Randomness, Non-determinism, and Symmetry Breaking

Trustees Of Boston University, Boston

Investigators

Abstract

Explosive development of computer technology outpaces theoretical understanding and leaves many of its pillars on shaky ground. As an extreme example, if it turns out that P=NP or that one-way functions do not exist, all of public-key cryptography and many tools crucial for national and personal security would be permanently incapacitated. In this (unlikely but possible) event, much of the computer infrastructure would have to be redesigned on a less impressive scale. On the other hand, many great advances cannot be foreseen even now due to insufficient theoretical understanding of basic issues. Computations rarely run in deterministic isolation. They interact with users and adversaries, with random events called by algorithms or generated by the context, with delays and glitches from the system, hardware, and distributed infrastructure, etc. Some of these interactions are hard to model, but even those with straightforward mathematical models are often very hard to analyze. Randomness and non-determinism are two basic "freedoms" branching out of the concept of deterministic computation which play a crucial role in computing theory. Yet our understanding of their role and power is minimal. Even a gradual progress in understanding these phenomena and their relationship to each other and to other concepts would be important. An example of achievements in this direction is the discovery of generic relationship between one-way functions and deterministic generation of randomness. Another is the concept of transparent (also called holographic, or PCP) proofs and computations. A number of interesting techniques useful for quite different results in these areas have been accumulated: low-degree polynomials and Fourier transforms over low-periodic groups, related to classical results on error-correcting codes and hashing, expander graphs, hierarchic structures, etc. The PI will continue his investigation of such concepts and of the power of these and other related techniques. Symmetry is one of the central phenomena in many fields. In computation it can simplify analysis, provide uniformity and redundancy useful, e.g., for error-correction. On the other hand, it can cause indecisiveness, deadlocks and complicate initialization and organization of computing processes. Breaking symmetries is as essential a task as maintaining them. A study of a number of mathematical and algorithmic tools useful for symmetry breaking is intended. Examples include Thue sequences, aperiodic tilings, extensions of the concept of flat connections from manifolds to graphs, and others. The work will advance discovery and understanding via dissemination of the results through talks, papers, and Web pages, PI's own and those of others. This research has implications in many close and remote areas. Indeed, the concepts the PI is interested in such as, e.g., randomness, are fundamental in a broad variety of fields of knowledge.