In this series, we’ll be exploring some of the material from the last chapter of Vadhan’s survey, in particular results of amplifying the hardness of computing functions and obtaining pseudorandom generators out of hard functions. In this relatively short post, by providing preliminary definitions and a motivation related to derandomization. We then close with a glimpse of our first step in hardness amplification.
Roughly speaking, generators are deterministic functions that stretch uniformly random seeds into bits that appear random. It turns out that our methods of quantifying “randomness” using both min-entropy and statistical difference from the uniform distribution are insufficient, because for any random variable and deterministic . In place of statistical or information theoretic measures, we thus use a complexity theoretical one: a variable will seem random if it is impossible for a so-called nonuniform algorithm running within a certain time limit to tell it apart from a uniformly random variable. We first define nonuniformity:
Definition 0: An algorithm deciding a language is -nonuniform for if there exist advice bitstrings each of length at most such that there exists a language decided by some algorithm where iff .
We will not make use of this definition in its full generality; it will suffice to talk about algorithms which operate with some “advice” hardwired in, and the length of this advice will be reasonable enough that we won’t bother with the data of the length function . We can now formalize our abovementioned ideas of “randomness” and pseudorandom generators.
Definition 1: Random variables and are (nonuniformly) computationally indistinguishable if for every nonuniform algorithm running in time at most , .
Definition 2: A -pseudorandom generator is a deterministic function such that and are -computationally indistinguishable.
Derandomizing BPP with Generators
It turns out that if we can find such a generator, we can effectively derandomize BPP. We will refer to generators as “computable in ” if we can determine the number of random bits needed to stretch to bits and run a uniform deterministic algorithm to calculate the generator’s output both in time . Later on, we will refer to generators as mildly explicit if they are computable in time polynomial in and .
Result 1: If for every there exists a pseudorandom generator computable in time , then BPP is strictly contained in DTIME.
Proof: Take a BPP algorithm for input and coin tosses , which we will take WLOG to be the circuit size simulating for some constant . To decide for , we can just write down for all sets of coin tosses and take the majority decision to be the output of our derandomized algorithm, and this takes as desired. To show that decides correctly more than half the time for every input , it suffices to observe that if it does not for some , the probability that outputs 1 exceeds by at least (the 1/3 comes from our definition of the error bound for BPP algorithms), contradicting the pseudorandomness of .
Tantalizingly, by substituting in asymptotics, this statement tells us that if we can find a mildly explicit -generator with seed logarithmic in output length, we can derandomize all of BPP into P! We will proceed beginning with the weakest possible assumptions about generators, and our final result will tell us either that we can indeed derandomize all of BPP into a subset E=DTIME of the DTIME class given above, or at least guarantee the existence of significantly faster algorithms for SAT and other common NP-complete problems!
To do this, we reduce the problem of finding mildly explicit generators to finding a function in E that is “hard on average to compute,” then use hardness amplification to show that it suffices to find a function in E that is only “hard to compute” in the worst case. We first define both notions of hardness:
Definitions 3,4: A Boolean function is -average-case hard if for every nonuniform probabilistic algorithm running within time , . On the other hand, is -worst-case hard if for all such algorithms , there exists some input such that .
We first show how to get a good generator out of an average-case hard function in , we first introduce the notion of next-bit unpredictability and its connection to generators:
Definition 5: A random variable on is -next-bit-unpredictable if for every and every nonuniform probabilistic algorithm (“predictor”) running within time , , where denotes the th bit of the value that takes on and where the probability is taken over all of and coin tosses
Result 2: If on is -next-bit-unpredictable, it is -pseudorandom.
Proof: Assume to the contrary that is not -pseudorandom so that there exists some nonuniform algorithm in time that distinguishes between and the uniform distribution on with advantage greater than . The key is that this advantage allows to predict future bits better than a random coin toss. What follows is a so-called “hybrid argument”: define to be the bitstring-valued random variable , where is the uniform distribution on . Because , there is some such that . Rewriting as
we find that . Now define a predictor by , where are uniformly random bits. By construction, the probability that the predictor succeeds exceeds , and by using the random bits as advice, we get a predictor that runs in the same time as , a contradiction of next-bit unpredictability.
Remark: In fact the converse is also true: -pseudorandomness implies -next-bit-unpredictability; the contrapositive is given by constructing an algorithm that outputs a 1 when the predictor succeeds and a zero otherwise, and the additive constant comes from adding logical gates to ‘s circuit to check for this success.
We can now prove our first main result, the reduction of finding mildly explicit generators to finding average-case-hard functions in E:
Result 3: Fix a time function that is computable in time exponential in its input. If there is some in E that on length- inputs is -average-case hard, there is a mildly explicit -generator with seed length .
Proof: As it turns out that with the above result, we’re almost done; we’ll just need appropriate asymptotics on seed length. The gist will be to evaluate our hard function on inputs that share only a few bits. Define an design to be a family of subsets of each of cardinality and mutually intersecting in at most elements. The key to getting the desired asymptotic bounds is the following lemma:
Lemma: For every and , there exists an -design such that and .
Proof: The proof is nonconstructive. We will show that an -design will exist as long as is bounded above by . Fix , and the probability that intersect in at least elements is . This tells us that for any , the expected number of sets among , by our choice of bound on , is strictly less than 1, so an -design on subsets is indeed possible. Stirling’s approximation on our inequality then gives the desired result.
Given an design and a function , we can get a generator by evaluating on the input restricted to each subset in the design. The generator given by is called the Nigan-Wigderson generator
Lemma: If is hard, then is -pseudorandom.
Proof: As usual, we prove the contrapositive. Say is not pseudorandom so that by our result on next-bit unpredictability, we have a -predictor and an index such that with probability more than . We can reduce the random choice of to a random choice of . Specifically, there must exist some fixed choice of bits for such that if we define to be the random variable such that equals this fixed choice and is uniformly distributed over bitstrings of length , then define the algorithm , which will compute the function with error less than . Because can be computed by storing as advice a lookup table of size at most and doing lookups with a circuit of size , the total time of is at most , so is not -hard, as desired.
The proof of result 2 follows by picking the appropriate parameters.
Hardness Amplification I: Worst-Case Hard to Constant Average-Case
Our next goal will be to construct a constant average-case-hard function out of a worst-case hard function using list decoding.
It turns out that if we view a worst-case hard function as a message and pass this through an encoding for which there exists an efficient decoding, then the codeword will be average-case hard. Unfortunately, decoding as we’ve defined it requires reading in all of the bits of the received word and writing out all of the bits of the decoded message, taking time that we might as well have used to make a gigantic truth table to compute to begin with. Instead, we introduce the following variant of decoding:
Definition 6: A local -decoding algorithm for an encoding is a probabilistic algorithm that, given oracle access to a received word and an input position , computes with probability 2/3 the value for any message whose encoding is -close to . For coin tosses , the output of the algorithm will be denoted by , and probability is taken over all .
Result 3: If the message in the above definition is worst-case hard for nonuniform time and runs in nonuniform time at most , then is -average-case hard.
Proof: Say that is not average-case hard so that there exists some algorithm running in time such that . There must exist some choice of coin tosses such that, defining deterministic nonuniform algorithm , we have . But this is just another word in the space , so this bound translates into . By definition, the algorithm computes to within constant error, and the circuit representing this algorithm is the circuit for with oracle gates replaced by the circuit for , so is not -worst-case-hard.
Our hardness amplification will reduce to a worst-case-hard function running in asymptotically the same time as the average-case-hard function, so we will want an encoding . Because our final result will be a statement about functions in exponential deterministic time, we also want our encoding to be of this complexity . We will also want the decoding not to take too much time, but we will determine later what the runtime for should be precisely. Lastly, to get rid of the term in our lemma on Nigan-Wigderson generators, we will want the code to have a binary alphabet.