A Computational View of Randomness

The current state of knowledge in Computational Complexity Theory suggests two strong empirical "facts" (whose truth are the two major open problems of this field).

• (1) Some natural computational tasks are infeasible
  (e.g. it seems so for computing the functions PERMANENT, FACTORING, CLIQUE, SATISFIABILITY ...)
• (2) Probabilistic algorithms can be much more efficient than deterministic ones.
  (e.g it seems so for PRIMALITY, VERIFYING IDENTITIES, APPROXIMATING VOLUMES...)

As it does with other notions (e.g. knowledge, proof..), Complexity Theory attempts to understand the notion of randomness from computational standpoint. One major achievement of this study is the following (surprising?) relation between these two "facts" above:

THEOREM: (1) contradicts (2)

In words: If ANY "natural" problem is "infeasible", then EVERY probabilistic algorithm can be "efficiently" "derandomized". I plan to explain the sequence of important ideas, definitions, and techniques developed in the last 20 years that enable a formal statement and proof of such a theorem. Many of them, such as the formal notions of "pseudo-random generator", and "computational indistinguishability" are of fundamental interest beyond derandomization; they have far reaching implications on our ability to build efficient cryptographic systems, as well as our inability to efficiently learn natural concepts and effectively prove natural mathematical conjectures (such as (1) above).

Tight Hardness vs. Randomness Trade-offs

The first talk explained that (computational) hardness can be effectively turned into (computational) randomness. In this talk we will be stingy and ask exactly how hard (and how easy) must a function be, so as to achieve complete or partial derandomization of all efficient probabilistic algorithms. Successively weakening the hardness assumptions should be viewed as part of a program leading (hopefully) to obtaining UNCONDITIONAL limits on the power of randomness, such as e.g. BPP EXP. I will talk mostly on one of the following two recent works with Russell Impagliazzo. The first work deals with non-uniform hardness assumptions. Here we achieve a tight trade-off: exponential circuit lower bounds on any problem in E suffice to prove BPP=P. The improvement over previous trade-offs come from a solution to another problem of independent interest: deterministic amplification of hardness. This construction turns a hard-on-average Boolean function on n bits into a function on O(n) bits that is nearly unpredictable. The second work deals with uniform hardness assumptions. Derandomization under such assumptions was known only for one-way functions. We show that at least for derandomizing algorithms in AvRP (namely probabilistic algorithms that work well for random inputs), it suffices to assume BPP EXP. The obvious difficulty is that the conversion of a distinguisher of the Nisan-Wigderson generator (which is the only known tool that can use hard functions that are not 1-way) into an efficient algorithm for the hard function it is based on looks inherently non-uniform. We overcome this difficulty using a novel bootstrapping strategy.

Both lectures will also be given April 8 and 9, 1998 as part of the Pacific Institute for the Mathematical Sciences Lecture Series at the University of British Columbia. Please contact David Austin (austin@math.ubc.ca) for details