# DIMACS Computer Science Department Colloquium Series - Princeton

## Title:

Computational Randomness - A survey

## Speaker:

- Avi Wigderson
- Institute for Advanced Study and Hebrew University

## Place:

- Room 105 (Small Auditorium)
- Computer Science Building
- Princeton University

## Time:

- 4:00 pm (Tea reception at 3:00 pm in the Tea Room)
- Wednesday, February 7, 1996

## 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 Boolean circuits,
then BPP=P (eg randomness is useless in efficient computation!).

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.

Host: Andrew Yao

Document last modified on January 22, 1996