Progress in Computer Science and Applied Logic – serie

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 methodologies and tools. One of these groups are the applied probabilists, many of whom consider their field an offspring of mathematics, and who find their motivation in many areas of application. The other is that group of computer scientists who, over the years, have found an increasing need in their work for the use of probabilistic models. The most visible area of common methodology between these two groups is networks of queues, Hhich by itself could have been the theme of an entire conference. FunctionQl areas which are, or are becoming, sources of exciting problems are computer performance analysis, data base analysis, analysis of communication protocols, data networks, and mixed voice-data telephone networks. The reader can add to this list by going through the papers in these Proceedings.

In the winter of 1978, Professor George P61ya and I jointly taught Stanford University's introductory combinatorics course. This was a great opportunity for me, as I had known of Professor P61ya since having read his classic book, How to Solve It, as a teenager. Working with P6lya, who ·was over ninety years old at the time, was every bit as rewarding as I had hoped it would be. His creativity, intelligence, warmth and generosity of spirit, and wonderful gift for teaching continue to be an inspiration to me. Combinatorics is one of the branches of mathematics that play a crucial role in computer sCience, since digital computers manipulate discrete, finite objects. Combinatorics impinges on computing in two ways. First, the properties of graphs and other combinatorial objects lead directly to algorithms for solving graph-theoretic problems, which have widespread application in non-numerical as well as in numerical computing. Second, combinatorial methods provide many analytical tools that can be used for determining the worst-case and expected performance of computer algorithms. A knowledge of combinatorics will serve the computer scientist well. Combinatorics can be classified into three types: enumerative, eXistential, and constructive. Enumerative combinatorics deals with the counting of combinatorial objects. Existential combinatorics studies the existence or nonexistence of combinatorial configurations.

-Ecclesiastes 12:12 Programs are invariably subjected to many rorms or transrormation. After an initial version of a program has been designed and developed, it undergoes debugging and certification. In addition, most long-lived pro­ grams have a liCe-cycle that includes modifications to meet amended specifications and extensions for expanded capabilities. Such evolution­ ary aspects of programming are the topic of this monograph. We present rormal methods for manipulating programs and illustrate their applica­ tion with numerous examples. Such methods could be incorporated in semi-automated programming environments, where they would serve to ease the burden on the programmer. We begin by describing a method whereby a given program that achieves one goal can be modified to achieve a different goal or a pro­ gram that computes wrong results can be debugged to achieve the 2 Preface intended results. The abstraction of a set of cognate programs to obtain a program schema, and the instantiation of abstract schemata to solve concrete problems, are approached from the same perspective. In addition, we describe synthesis rules for generating code from specifications and annotation rules for making assertions about code. The synthesis rules may be used when a program is first being developed, or when, in the course of modifying a program, the need arises to rewrite a program segment. Annotation rules may be used for the purpose of determining what an incorrect program really does before attempting to debug it or how a correct program works before attempting to modify it.

Hashing algorithms scramble data and create pseudo-uniform data distribu- tions. Bucket algorithms operate on raw untransformed data which are parti- tioned Into groups according to membership In equl-slzed d-dlmenslonal hyperrec- tangles, called cells or buckets. The bucket data structure Is rather sensitive to the distribution of the data. In these lecture notes, we attempt to explain the connection between the expected time of various bucket algorithms and the dis- tribution of the data. The results are Illustrated on standard searching, sorting and selection problems, as well as on a variety of problems In computational geometry and operations research. The notes grew partially from a graduate course on probability theory In computer science. I wish to thank Elizabeth Van Gulick for her help with the manuscript, and David Avis, Hanna AYukawa, Vasek Chvatal, Beatrice Devroye, Hossam EI Glndy, Duncan McCallum, Magda McCallum, Godfrled Toussaint and Sue Whltesldes"for making the School of Computer Science at McGill University such an enjoyable place. The work was supported by NSERC Grant A3456 and by FCAC Grant EQ-1679.INTRODUCTION 1 INTRODUCTION It Is not a secret that methods based upon the truncation of data have good expected time performance. For example, for nice distributions of the data, searching Is often better done via a hashing data structure Instead of via a search tree. The speed one observes In practice Is due to the fact that the truncation operation Is a constant time operation.

I wonder whether Karel Capek imagined in 1923 that by his use of the Czech word for forced labor, rohota, to name the android creations of Mr. Rossum he was naming an important technology of his future. Perhaps it wasn't Capek's work directly, but rather its influence on Lang's movie Metropolis in 1926 that introduced the term to the popular consciousness. In the public mind ever since a robot has been a me­ chanical humanoid, tireless and somewhat sinister. In the research community the field of robotics has recently reached large size and respectability, but without answering the question, "What is robotics?" or perhaps, "What is a robot?" There is no real consensus for a precise definition of robotics. I suppose that Capekian mechanical men, if one could build them, are robots, but after that there is little agreement. Rather than try to enumerate all of the things that are and are not robots, I will try to characterize the kinds of features that make a system a robot. A candidate definition of a robot is a system intended to achieve mechanical action, with sensory feedback from the world to guide the actions and a sophisticated con­ trol system connecting the sensing and the actions.

A so-called "effective" algorithm may require arbitrarily large finite amounts of time and space resources, and hence may not be practical in the real world. A "feasible" algorithm is one which only requires a limited amount of space and/or time for execution; the general idea is that a feasible algorithm is one which may be practical on today's or at least tomorrow's computers. There is no definitive analogue of Church's thesis giving a mathematical definition of feasibility; however, the most widely studied mathematical model of feasible computability is polynomial-time computability. Feasible Mathematics includes both the study of feasible computation from a mathematical and logical point of view and the reworking of traditional mathematics from the point of view of feasible computation. The diversity of Feasible Mathematics is illustrated by the. contents of this volume which includes papers on weak fragments of arithmetic, on higher type functionals, on bounded linear logic, on sub recursive definitions of complexity classes, on finite model theory, on models of feasible computation for real numbers, on vector spaces and on recursion theory. The vVorkshop on Feasible Mathematics was sponsored by the Mathematical Sciences Institute and was held at Cornell University, June 26-28, 1989.

The origins of this monograph lie in my Ph.D. dissertation of 1987 at the University of Pennsylvania, which was concerned with proof procedures for the Horn clause subset of logic. The rise of logic programming has made this an important area of study. All Prologs are based on a variant of resolution, and inherit various properties related to this proof method. This monograph studies the paradigm of logic programming in the context of graph-based proof procedures which are unrelated to resolution. The monograph is not a general introduction to logic programming, although it is self-contained with respect to the mathematics used. It should appeal to the computer scientist or mathematician interested in the general area we now call computational logic. A large part of the monograph is devoted to detailed proofs that the methods we present are sound and complete, which in the context of the logic programming, means that the operational and denotational semantics agree.

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 providing a clean separation of the logical issues from the specification of procedural information, and amounts to a set of 'inference rules' for unification, hence the title of this book. We derive the set of transformations for general E-unification and higher­ order unification from an analysis of the sense in which terms are 'the same' after application of a unifying substitution. In both cases, this results in a simple extension of the set of basic transformations given by Herbrand­ Martelli-Montanari for standard unification, and shows clearly the basic relationships of the fundamental operations necessary in each case, and thus the underlying structure of the most important classes of term unifi­ cation problems.

Anil Nerode, Director of the Mathematics Institute at Cornell, USA, is one of the most influential logicians in the world. This volume, published in his honour, contains much new and significant work. The papers in this book are principally concerned with mathematical logic and some of its applications in computing. The book contains papers on recursion theory, intuitionism, computability in group theory, recursive model theory, reverse mathematics and the extraction of programs from proofs. A survey of Nerode's technical achievements over the last 30 years is also included. In particular, the book features papers on new developments in the understanding of the properties of intuitionistic set theory and intuitionistic analysis, the extension of computability in ordinary mathematics pioneered by Marian Boykan Pour-El and Ian Richards, the proof-theoretic strength of a long-standing conjecture of Fraisse and an extension of, and further account of, the Curry-Howard method of extracting programs from logical proofs. The papers in general arose from the conference, "Logical Methods in Mathematics and Computer Science.A Symposium in Honor of Anil Nerode on the Occasion of his Sixtieth Birthday", held at the Mathematical Sciences Institute at Cornell University, from June 1-3, 1992.

The field of computational learning theory arose out of the desire to for­ mally understand the process of learning. As potential applications to artificial intelligence became apparent, the new field grew rapidly. The learning of geo­ metric objects became a natural area of study. The possibility of using learning techniques to compensate for unsolvability provided an attraction for individ­ uals with an immediate need to solve such difficult problems. Researchers at the Center for Night Vision were interested in solving the problem of interpreting data produced by a variety of sensors. Current vision techniques, which have a strong geometric component, can be used to extract features. However, these techniques fall short of useful recognition of the sensed objects. One potential solution is to incorporate learning techniques into the geometric manipulation of sensor data. As a first step toward realizing such a solution, the Systems Research Center at the University of Maryland, in conjunction with the Center for Night Vision, hosted a Workshop on Learning and Geometry in January of 1991. Scholars in both fields came together to learn about each others' field and to look for common ground, with the ultimate goal of providing a new model of learning from geometrical examples that would be useful in computer vision. The papers in the volume are a partial record of that meeting.

One of the major concerns of theoretical computer science is the classifi­ cation of problems in terms of how hard they are. The natural measure of difficulty of a function is the amount of time needed to compute it (as a function of the length of the input). Other resources, such as space, have also been considered. In recursion theory, by contrast, a function is considered to be easy to compute if there exists some algorithm that computes it. We wish to classify functions that are hard, i.e., not computable, in a quantitative way. We cannot use time or space, since the functions are not even computable. We cannot use Turing degree, since this notion is not quantitative. Hence we need a new notion of complexity-much like time or spac~that is quantitative and yet in some way captures the level of difficulty (such as the Turing degree) of a function.

The purpose of this monograph is to provide the mathematically literate reader with an accessible introduction to the theory of quantum computing algorithms, one component of a fascinating and rapidly developing area which involves topics from physics, mathematics, and computer science. The author briefly describes the historical context of quantum computing and provides the motivation, notation, and assumptions appropriate for quantum statics, a non-dynamical, finite dimensional model of quantum mechanics. This model is then used to define and illustrate quantum logic gates and representative subroutines required for quantum algorithms. A discussion of the basic algorithms of Simon and of Deutsch and Jozsa sets the stage for the presentation of Grover's search algorithm and Shor's factoring algorithm, key algorithms which crystallized interest in the practicality of quantum computers. A group theoretic abstraction of Shor's algorithms completes the discussion of algorithms.The last third of the book briefly elaborates the need for error- correction capabilities and then traces the theory of quantum error- correcting codes from the earliest examples to an abstract formulation in Hilbert space. This text is a good self-contained introductory resource for newcomers to the field of quantum computing algorithms, as well as a useful self-study guide for the more specialized scientist, mathematician, graduate student, or engineer. Readers interested in following the ongoing developments of quantum algorithms will benefit particularly from this presentation of the notation and basic theory.

Automata and Their Applications is a uniform treatment of the theory of finite state machines on finite and infinite strings and trees. Many books deal with automata on finite strings, but there are very few expositions that prove the fundamental results of automata on infinite strings and trees. These results have important applications to modeling parallel computation and concurrency, the specification and verification of sequential and concurrent programs, databases, operating systems, computational complexity, and decision methods in logic and algebra. Thus, this textbook fills an important gap in the literature. Beginning with coverage of all standard fundamental results regarding finite automata, the book deals Buchi and Rabin automata and their applications to operating systems, temporal logic and communication systems, as well as to various logical theories. The book is self-contained with numerous examples, illustrations, exercises, and is suitable for a two-semester undergraduate course or a one-semester graduate course/seminar.Since no advanced mathematical background is required, the text is also useful for self-study by computer science professionals who wish to understand the foundations of modern formal approaches to software development, validation, and verification.

Networks have become nearly ubiquitous and increasingly complex, and their support of modern enterprise environments has become fundamental. Accordingly, robust network management techniques are essential to ensure optimal performance of these networks. This monograph treats the application of numerous graph-theoretic algorithms to a comprehensive analysis of dynamic enterprise networks. Network dynamics analysis yields valuable information about network performance, efficiency, fault prediction, cost optimization, indicators and warnings.Based on many years of applied research of generic network dynamics, this work covers a number of elegant applications (including many new and experimental results) of traditional graph theory algorithms and techniques to computationally tractable network dynamics analysis to motivate network analysts, practitioners and researchers alike. The material is also suitable for graduate courses addressing state-of-the-art applications of graph theory in analysis of dynamic communication networks, dynamic databasing, and knowledge management.

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 methodologies and tools. One of these groups are the applied probabilists, many of whom consider their field an offspring of mathematics, and who find their motivation in many areas of application. The other is that group of computer scientists who, over the years, have found an increasing need in their work for the use of probabilistic models. The most visible area of common methodology between these two groups is networks of queues, Hhich by itself could have been the theme of an entire conference. FunctionQl areas which are, or are becoming, sources of exciting problems are computer performance analysis, data base analysis, analysis of communication protocols, data networks, and mixed voice-data telephone networks. The reader can add to this list by going through the papers in these Proceedings.

The theory of finite automata on finite stings, infinite strings, and trees has had a dis­ tinguished history. First, automata were introduced to represent idealized switching circuits augmented by unit delays. This was the period of Shannon, McCullouch and Pitts, and Howard Aiken, ending about 1950. Then in the 1950s there was the work of Kleene on representable events, of Myhill and Nerode on finite coset congruence relations on strings, of Rabin and Scott on power set automata. In the 1960s, there was the work of Btichi on automata on infinite strings and the second order theory of one successor, then Rabin's 1968 result on automata on infinite trees and the second order theory of two successors. The latter was a mystery until the introduction of forgetful determinacy games by Gurevich and Harrington in 1982. Each of these developments has successful and prospective applications in computer science. They should all be part of every computer scientist's toolbox. Suppose that we take a computer scientist's point of view. One can think of finite automata as the mathematical representation of programs that run us­ ing fixed finite resources. Then Btichi's SIS can be thought of as a theory of programs which run forever (like operating systems or banking systems) and are deterministic. Finally, Rabin's S2S is a theory of programs which run forever and are nondeterministic. Indeed many questions of verification can be decided in the decidable theories of these automata.

The twenty-six papers in this volume reflect the wide and still expanding range of Anil Nerode's work. A conference on Logical Methods was held in honor of Nerode's sixtieth birthday (4 June 1992) at the Mathematical Sciences Institute, Cornell University, 1-3 June 1992. Some of the conference papers are here, but others are from students, co-workers and other colleagues. The intention of the conference was to look forward, and to see the directions currently being pursued, in the development of work by, or with, Nerode. Here is a brief summary of the contents of this book. We give a retrospective view of Nerode's work. A number of specific areas are readily discerned: recursive equivalence types, recursive algebra and model theory, the theory of Turing degrees and r.e. sets, polynomial-time computability and computer science. Nerode began with automata theory and has also taken a keen interest in the history of mathematics. All these areas are represented. The one area missing is Nerode's applied mathematical work relating to the environment. Kozen's paper builds on Nerode's early work on automata. Recursive equivalence types are covered by Dekker and Barback, the latter using directly a fundamental metatheorem of Nerode. Recursive algebra is treated by Ge & Richards (group representations). Recursive model theory is the subject of papers by Hird, Moses, and Khoussainov & Dadajanov, while a combinatorial problem in recursive model theory is discussed in Cherlin & Martin's paper. Cenzer presents a paper on recursive dynamics.

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 providing a clean separation of the logical issues from the specification of procedural information, and amounts to a set of 'inference rules' for unification, hence the title of this book. We derive the set of transformations for general E-unification and higher­ order unification from an analysis of the sense in which terms are 'the same' after application of a unifying substitution. In both cases, this results in a simple extension of the set of basic transformations given by Herbrand­ Martelli-Montanari for standard unification, and shows clearly the basic relationships of the fundamental operations necessary in each case, and thus the underlying structure of the most important classes of term unifi­ cation problems.

One of the major concerns of theoretical computer science is the classifi­ cation of problems in terms of how hard they are. The natural measure of difficulty of a function is the amount of time needed to compute it (as a function of the length of the input). Other resources, such as space, have also been considered. In recursion theory, by contrast, a function is considered to be easy to compute if there exists some algorithm that computes it. We wish to classify functions that are hard, i.e., not computable, in a quantitative way. We cannot use time or space, since the functions are not even computable. We cannot use Turing degree, since this notion is not quantitative. Hence we need a new notion of complexity-much like time or spac~that is quantitative and yet in some way captures the level of difficulty (such as the Turing degree) of a function.

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 ideas used for computing "spline" curves can be extended to allow us to compute "spline" surfaces. The application ofthese mathematical ideas is rather widespread. Spline functions are central to computer graphics disciplines. Spline curves and surfaces are used in computer graphics renderings for both real and imagi­ nary objects. Computer-aided-design (CAD) systems depend on algorithms for computing spline functions, and splines are used in numerical analysis and statistics. Thus the construction of movies and computer games trav­ els side-by-side with the art of automobile design, sail construction, and architecture; and statisticians and applied mathematicians use splines as everyday computational tools, often divorced from graphic images.

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 Benioff [6]' [7] who considered a quantum mechanical model of computers and the computation process. A related question was discussed shortly thereafter by Richard Feynman [35] who began from a different perspec­ tive by asking what kind of computer should be used to simulate physics. His analysis led him to the belief that with a suitable class of "quantum machines" one could imitate any quantum system.

Perspicuity is part of proof. If the process by means of which I get a result were not surveyable, I might indeed make a note that this number is what comes out - but what fact is this supposed to confirm for me? I don't know 'what is supposed to come out' . . . . 1 -L. Wittgenstein A feasible computation uses small resources on an abstract computa­ tion device, such as a 'lUring machine or boolean circuit. Feasible math­ ematics concerns the study of feasible computations, using combinatorics and logic, as well as the study of feasibly presented mathematical structures such as groups, algebras, and so on. This volume contains contributions to feasible mathematics in three areas: computational complexity theory, proof theory and algebra, with substantial overlap between different fields. In computational complexity theory, the polynomial time hierarchy is characterized without the introduction of runtime bounds by the closure of certain initial functions under safe composition, predicative recursion on notation, and unbounded minimization (S. Bellantoni); an alternative way of looking at NP problems is introduced which focuses on which pa­ rameters of the problem are the cause of its computational complexity and completeness, density and separation/collapse results are given for a struc­ ture theory for parametrized problems (R. Downey and M. Fellows); new characterizations of PTIME and LINEAR SPACE are given using predicative recurrence over all finite tiers of certain stratified free algebras (D.

The field of computational learning theory arose out of the desire to for­ mally understand the process of learning. As potential applications to artificial intelligence became apparent, the new field grew rapidly. The learning of geo­ metric objects became a natural area of study. The possibility of using learning techniques to compensate for unsolvability provided an attraction for individ­ uals with an immediate need to solve such difficult problems. Researchers at the Center for Night Vision were interested in solving the problem of interpreting data produced by a variety of sensors. Current vision techniques, which have a strong geometric component, can be used to extract features. However, these techniques fall short of useful recognition of the sensed objects. One potential solution is to incorporate learning techniques into the geometric manipulation of sensor data. As a first step toward realizing such a solution, the Systems Research Center at the University of Maryland, in conjunction with the Center for Night Vision, hosted a Workshop on Learning and Geometry in January of 1991. Scholars in both fields came together to learn about each others' field and to look for common ground, with the ultimate goal of providing a new model of learning from geometrical examples that would be useful in computer vision. The papers in the volume are a partial record of that meeting.

This innovative monograph explores a new mathematical formalism in higher-order temporal logic for proving properties about the behavior of systems. Developed by the authors, the goal of this novel approach is to explain what occurs when multiple, distinct system components interact by using a category-theoretic description of behavior types based on sheaves. The authors demonstrate how to analyze the behaviors of elements in continuous and discrete dynamical systems so that each can be translated and compared to one another. Their temporal logic is also flexible enough that it can serve as a framework for other logics that work with similar models. The book begins with a discussion of behavior types, interval domains, and translation invariance, which serves as the groundwork for temporal type theory. From there, the authors lay out the logical preliminaries they need for their temporal modalities and explain the soundness of those logical semantics. These results are then applied to hybrid dynamical systems, differential equations, and labeled transition systems. A case study involving aircraft separation within the National Airspace System is provided to illustrate temporal type theory in action.  Researchers in computer science, logic, and mathematics interested in topos-theoretic and category-theory-friendly approaches to system behavior will find this monograph to be an important resource.  It can also serve as a supplemental text for a specialized graduate topics course.

Mathematical logic is a branch of mathematics that takes axiom systems and mathematical proofs as its objects of study. This book shows how it can also provide a foundation for the development of information science and technology. The first five chapters systematically present the core topics of classical mathematical logic, including the syntax and models of first-order languages, formal inference systems, computability and representability, and Gödel’s theorems. The last five chapters present extensions and developments of classical mathematical logic, particularly the concepts of version sequences of formal theories and their limits, the system of revision calculus, proschemes (formal descriptions of proof methods and strategies) and their properties, and the theory of inductive inference. All of these themes contribute to a formal theory of axiomatization and its application to the process of developing information technology and scientific theories. The book also describes the paradigm of three kinds of language environments for theories and it presents the basic properties required of a meta-language environment. Finally, the book brings these themes together by describing a workflow for scientific research in the information era in which formal methods, interactive software and human invention are all used to their advantage.The second edition of the book includes major revisions on the proof of the completeness theorem of the Gentzen system and new contents on the logic of scientific discovery, R-calculus without cut, and the operational semantics of program debugging.This book represents a valuable reference for graduate and undergraduate students and researchers in mathematics, information science and technology, and other relevant areas of natural sciences. Its first five chapters serve as an undergraduate text in mathematical logic and the last five chapters are addressed to graduate students inrelevant disciplines.

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 emphasis is on obtaining unconditional rigorously proved statements. The bright side of this approach is that the results do not depend on any assumptions or conjectures. On the downside, the results are much weaker than those which are widely believed to be true. We obtain several lower bounds, exponential in terms of logp, on the degrees and orders of o polynomials; o algebraic functions; o Boolean functions; o linear recurrence sequences; coinciding with values of the discrete logarithm modulo a prime p at sufficiently many points (the number of points can be as small as pI/2+O:). These functions are considered over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1. The case of d = 2 is of special interest since it corresponds to the representation of the rightmost bit of the discrete logarithm and defines whether the argument is a quadratic residue.

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 event followed the concept of the research programs at such well-known research institutions as the Newton Institute (UK), Oberwolfach and Dagstuhl (Germany), and Luminy (France). Accordingly, there were only invited lectures at the workshop with plenty of time for informal discussions. It was hoped and successfully achieved that the meeting would encourage and stimulate further research in information and computer security as well as in the design and implementation of number theoretic cryptosystems and other related areas. Another goal of the meeting was to stimulate collaboration and more active interaction between mathematicians, computer scientists, practical cryptographers and engineers in academia, industry and government.