Using Hard Problems to Create Pseudorandom Generators

Noam Nisan

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-88-486

, 1988

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-486.pdf

This thesis describes two methods of constructing pseudorandom generators from hard problems. We first give a simple and very general construction of pseudorandom generators. They stretch a short string of truly random bits into a long string that looks random to any algorithm from a complexity class C (e.g. P, NC, PSPACE, ...) using an arbitrary function that is hard for C. This construction reveals an equivalence between the problems of proving certain lower bounds and of constructing pseudorandom generators. This construction has many consequences. The most direct one is that efficient deterministic simulation of randomized algorithms is possible under much weaker assumptions than previously known. The efficiency of the simulations depends on the strength of the assumptions, and may achieve P=BPP. We believe that our results are very strong evidence that the gap between randomized and deterministic complexity is not large. Using the known lower bounds for constant depth circuits, our construction yields unconditionally proven pseudorandom generators for constant depth circuits. As an application we characterize the power of NP with a random oracle. Our second pseudorandom generator stretches short truly random strings to long strings that look random to all Logspace machines. This is proved without relying on any unproven assumptions. Instead, we use lower bounds on the complexity of the following multiparty communication game: Let f(x1, ... ,xk) be a Boolean function that k parties wish to collaboratively evaluate. The ith party knows each input argument except xi; and each party has unlimited computational power. They share a blackboard, viewed by all parties, where they can exchange messages. The objective is to minimize the number of bits written on the board. We prove lower bounds on the number of bits that need to be written on the board in order to compute a certain function. We then use these bounds to construct a pseudorandom generator for Logspace. As an application we present an explicit construction of universal traversal sequences for general graphs.

Advisors: Richard M. Karp

BibTeX citation:

@phdthesis{Nisan:CSD-88-486,
    Author= {Nisan, Noam},
    Title= {Using Hard Problems to Create Pseudorandom Generators},
    School= {EECS Department, University of California, Berkeley},
    Year= {1988},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6148.html},
    Number= {UCB/CSD-88-486},
    Abstract= {This thesis describes two methods of constructing pseudorandom generators from hard problems. <p>We first give a simple and very general construction of pseudorandom generators. They stretch a short string of truly random bits into a long string that looks random to any algorithm from a complexity class <i>C</i> (e.g. P, NC, PSPACE, ...) using an arbitrary function that is hard for <i>C</i>. This construction reveals an equivalence between the problems of proving certain lower bounds and of constructing pseudorandom generators. <p>This construction has many consequences. The most direct one is that efficient deterministic simulation of randomized algorithms is possible under much weaker assumptions than previously known. The efficiency of the simulations depends on the strength of the assumptions, and may achieve <i>P</i>=<i>BPP</i>. We believe that our results are very strong evidence that the gap between randomized and deterministic complexity is not large. <p>Using the known lower bounds for constant depth circuits, our construction yields unconditionally proven pseudorandom generators for constant depth circuits. As an application we characterize the power of NP with a random oracle. <p>Our second pseudorandom generator stretches short truly random strings to long strings that look random to all Logspace machines. This is proved without relying on any unproven assumptions. Instead, we use lower bounds on the complexity of the following multiparty communication game: <p>Let <i>f</i>(<i>x</i>1, ... ,<i>x</i>k) be a Boolean function that <i>k</i> parties wish to collaboratively evaluate. The <i>i</i>th party knows each input argument except <i>x</i>i; and each party has unlimited computational power. They share a blackboard, viewed by all parties, where they can exchange messages. The objective is to minimize the number of bits written on the board. <p>We prove lower bounds on the number of bits that need to be written on the board in order to compute a certain function. We then use these bounds to construct a pseudorandom generator for Logspace. As an application we present an explicit construction of universal traversal sequences for general graphs.},
}

EndNote citation:

%0 Thesis
%A Nisan, Noam 
%T Using Hard Problems to Create Pseudorandom Generators
%I EECS Department, University of California, Berkeley
%D 1988
%@ UCB/CSD-88-486
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6148.html
%F Nisan:CSD-88-486