Notes of Oded Goldreich’s talk

In a world of {BPP=P}

It has been known for a long time that existence of suitable pseudorandom generators implies that {BPP=P}, i.e. every problem solvable by a probabilistic polynomial alogorthm can be derandomized. I claim that the converse is true. If it happens that {BPP=P}, then pseudorandom generators exist.

1. Pseudorandom generators

1.1. Definition

A pseudorandom generator is a deterministic algorithm which produces long strings which look random from short strings which are truly random. This covers a variety of devices, from general purpose PRGs fooling any efficient observer to special purpose, say pairwise independence generators. The parameters of a PRG are

  1. Amount of stretching.
  2. Level of “looking random”.
  3. Computational cost of the algorithm.

1.2. Derandomization

For derandomizing, it is sufficient to use PRGs that run in time exponential in seed length, whose output looks random to linear-time observers. Indeed, one hopes the stretch to be exponential. Thus requirements on PRGs are much relaxed compared to usual requirements.

Theorem 1 If PRGs that run in time exponential in seed length, have exponential stretch and whose output looks random to linear-time observers exist, then {BPP=P}.

Proof: First assume the algorithm to be derandomize has linear running time. Combine it with PRG to get a randomized algorithm which is functionally equivalent, has polynomial running time, and uses {\log n} random bits. Then derandomize by brutally running on all possible values of bits previously thought of as random. \Box

“Random looking” is specified as follows. For every polynomial {P}, no probabilistic {P(n)}-time algorithm can distinguish the PRG’s output from a truly random string with gap {>\frac{1}{P(n)}}.

With this uniform formulation, we can put {BPP} effectively in {P}. I.e. for every problem in {BPP} and every polynomial {P}, we obtain a deterministic polytime algorithm such that no {P(n)}-time algorithm can find an input on which the algorithm errs. We call this {P}-effectively solving the problem.

2. Reversing the connection

Assume {BPP=P}. The goal is to construct PRGs.

A random function of exponential stretch has the desired pseudorandomness feature. Idea: Just derandomize this choice! But this is a search problem, and {BPP} deals with decision problems and not search problems. So we must first reduce {BPP}-search problems to {BPP}-decision problems.

2.1. From {BPP}-search problems to {BPP}-decision problems

Here is our current search problem: Wanted PRG is, for each {n}, a set {S_n} of length {n} strings, such that uniform distribution on {S_n} fools {P(n)}-time observers. Note that validity of solutions can be checked in probabilistic polynomial time.

More generally, {BPP}-search problems require finding PPT

Claim: Every {BPP}-search problem reduces to a {BPP}-decision problem.

Remiscent of reduction of {P}-search problems to {P}-decision problems, which goes as follows: consider the following sequence of decision problems: given a prefix {w_1 \cdots w_k}, is one of {w_1 \cdots w_k 0} and {w_1 \cdots w_k 1} the prefix of a solution ?

Here, need merely an estimate on the probability that a prefix {w_1 \cdots w_k} does extend into a prefix of a solution.

2.2. Targeted derandomizers

Above construction merely shows that {BPP} problems can be effectively solved by deterministic algorithms with small error. This is not quite {BPP=P}.

Theorem 2 {BPP=P} iff there exists a targeted derandomizer of exponential stretch.

A targeted derandomizer is a family of PRGs. Think of auxiliary parameter as describing the environment. The observer knows it as well as the generator, and nevertheless, must be fooled uniformly whatever the state of the environment.

see my paper and my slides.

About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See http://www.math.ens.fr/metric2011/
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s