These two volumes are the Proceedings of the first special interest meeting instigated and organized by the joint Technical Section and College in Applied Probability of ORSA and THlS. This meeting, which took place January 5-7, 1981 at Florida Atlantic University in Boca Raton, Florida, had the same name as these Proceedings: Applied Probability-Computer Science, the Interface. The goal of that conference was to achieve a meeting of, and a cross fertilization between, two groups of researchers who, from different starting points, had come to work on similar problems, often developing similar...

In this monograph we study two generalizations of standard unification, E-unification and higher-order unification, using an abstract approach orig- inated by Herbrand and developed in the case of standard first-order unifi- cation by Martelli and Montanari. The formalism presents the unification computation as a set of non-deterministic transformation rules for con- verting a set of equations to be unified into an explicit representation of a unifier (if such exists). This provides an abstract and mathematically elegant means of analysing the properties of unification in various settings by...

A spline is a thin flexible strip composed of a material such as bamboo or steel that can be bent to pass through or near given points in the plane, or in 3-space in a smooth manner. Mechanical engineers and drafting specialists find such (physical) splines useful in designing and in drawing plans for a wide variety of objects, such as for hulls of boats or for the bodies of automobiles where smooth curves need to be specified. These days, physi- cal splines are largely replaced by computer software that can compute the desired curves (with appropriate encouragment). The same mathematical...

In 1994 Peter Shor 65] published a factoring algorithm for a quantum computer that finds the prime factors of a composite integer N more efficiently than is possible with the known algorithms for a classical com- puter. Since the difficulty of the factoring problem is crucial for the se- curity of a public key encryption system, interest (and funding) in quan- tum computing and quantum computation suddenly blossomed. Quan- tum computing had arrived. The study of the role of quantum mechanics in the theory of computa- tion seems to have begun in the early 1980s with the publications of Paul...

The book introduces new techniques that imply rigorous lower bounds on the com- plexity of some number-theoretic and cryptographic problems. It also establishes certain attractive pseudorandom properties of various cryptographic primitives. These methods and techniques are based on bounds of character sums and num- bers of solutions of some polynomial equations over finite fields and residue rings. Other number theoretic techniques such as sieve methods and lattice reduction algorithms are used as well. The book also contains a number of open problems and proposals for further research. The...

This volume contains the refereed proceedings of the Workshop on Cryptography and Computational Number Theory, CCNT'99, which has been held in Singapore during the week of November 22-26, 1999. The workshop was organized by the Centre for Systems Security of the Na- tional University of Singapore. We gratefully acknowledge the financial support from the Singapore National Science and Technology Board under the grant num- ber RP960668/M. The idea for this workshop grew out of the recognition of the recent, rapid development in various areas of cryptography and computational number the- ory....

The book introduces new techniques which imply rigorous lower bounds on the complexity of some number theoretic and cryptographic problems. These methods and techniques are based on bounds of character sums and numbers of solutions of some polynomial equations over finite fields and residue rings. It also contains a number of open problems and proposals for further research. We obtain several lower bounds, exponential in terms of logp, on the de- grees and orders of - polynomials; - algebraic functions; - Boolean functions; - linear recurring sequences; coinciding with values of the discrete...

Symbolic rewriting techniques are methods for deriving consequences from systems of equations, and are of great use when investigating the structure of the solutions. Such techniques appear in many important areas of research within computer algebra: - the Knuth-Bendix completion for groups, monoids and general term-rewriting systems, - the Buchberger algorithm for Grobner bases, - the Ritt-Wu characteristic set method for ordinary differential equations, and - the Riquier-Janet method for partial differential equations. This volume contains invited and contributed papers to the Symbolic...

This book brings together contributions by leading researchers in computational complexity theory written in honor of Somenath Biswas on the occasion of his sixtieth birthday. They discuss current trends and exciting developments in this flourishing area of research and offer fresh perspectives on various aspects of complexity theory. The topics covered include arithmetic circuit complexity, lower bounds and polynomial identity testing, the isomorphism conjecture, space-bounded computation, graph isomorphism, resolution and proof complexity, entropy and randomness. Several chapters have a...