DIMACS Theory of Computing Seminar

Title:

Computational Randomness - A Survey

Speaker:

Avi Wigderson

Hebrew University

(Visiting IAS and Princeton University)

Place:

Room 252, Hill Center

Busch Campus, Rutgers University.

Time:

4:30 PM

Thursday, September 21, 1995

Abstract:

One of the most fundamental discoveries of Complexity Theory is the connection between Hardness and Randomness: the harder it is to solve certain natural problems, the cheaper it is to eliminate randomness from probabilistic algorithms.

I will survey the ideas that led to this understanding, and in particular the main concept of a pseudo-random generator. Two fundamentally different constructions of such generators are known:

1) Generators based on one-way functions, yielding theorems like:

Theorem 1: If FACTORING has no subexponential size circuits, then BPP=P

2) Generators based on arbitrary hard functions in EXP, yielding e.g.

Theorem 2: If PERMANENT has no subexponential size circuits, then BPP=P

I will describe the costructions of both types of generators, the relative merits of both types, other applications and open problems.

Document last modified on September 15, 1995