Derandomization: a brief overview
---
paper_title: Randomized Algorithms

paper_content:

For many applications, a randomized algorithm is either the simplest or the fastest algorithm available, and sometimes both. This book introduces the basic concepts in the design and analysis of randomized algorithms. The first part of the text presents basic tools such as probability theory and probabilistic analysis that are frequently used in algorithmic applications. Algorithmic examples are also given to illustrate the use of each tool in a concrete setting. In the second part of the book, each chapter focuses on an important area to which randomized algorithms can be applied, providing a comprehensive and representative selection of the algorithms that might be used in each of these areas. Although written primarily as a text for advanced undergraduates and graduate students, this book should also prove invaluable as a reference for professionals and researchers.
---
paper_title: How to generate cryptographically strong sequences of pseudo random bits

paper_content:

We give a set of conditions that allow one to generate 50–50 unpredictable bits.Based on those conditions, we present a general algorithmic scheme for constructing polynomial-time deterministic algorithms that stretch a short secret random input into a long sequence of unpredictable pseudo-random bits.We give an implementation of our scheme and exhibit a pseudo-random bit generator for which any efficient strategy for predicting the next output bit with better than 50–50 chance is easily transformable to an “equally efficient” algorithm for solving the discrete logarithm problem. In particular: if the discrete logarithm problem cannot be solved in probabilistic polynomial time, no probabilistic polynomial-time algorithm can guess the next output bit better than by flipping a coin: if “head” guess “0”, if “tail” guess “1”
---
paper_title: On the generation of cryptographically strong pseudo-random sequences

paper_content:

In this paper we show how to generate from a short random seed S a long sequence of pseudo-random numbers Ri in which the problem of computing one more Ri value given an arbitrarily large subset of the other values is provably equivalent to the cryptanalysis of the associated Rivest-Shamir-Adleman encryption function.
---
paper_title: A hard-core predicate for all one-way functions

paper_content:

A central tool in constructing pseudorandom generators, secure encryption functions, and in other areas are “hard-core” predicates b of functions (permutations) ƒ, discovered in [Blum Micali 82]. Such b ( x ) cannot be efficiently guessed (substantially better than 50-50) given only ƒ( x ). Both b , ƒ are computable in polynomial time. [Yao 82] transforms any one-way function ƒ into a more complicated one, ƒ * , which has a hard-core predicate. The construction applies the original ƒ to many small pieces of the input to ƒ * just to get one “hard-core” bit. The security of this bit may be smaller than any constant positive power of the security of ƒ. In fact, for inputs (to ƒ * ) of practical size, the pieces effected by ƒ are so small that ƒ can be inverted (and the “hard-core” bit computed) by exhaustive search. In this paper we show that every one-way function, padded to the form ƒ( p , x ) = ( p , g ( x )), VV p VV = V x V, has by itself a hard-core predicate of the same (within a polynomial) security. Namely, we prove a conjecture of [Levin 87, sec. 5.6.2] that the scalar product of Boolean vectors p , x is a hard-core of every one-way function ƒ( p , x ) = ( p , g ( x )). The result extends to multiple (up to the logarithm of security) such bits and to any distribution on the x 's for which ƒ is hard to invert.
---
paper_title: One-way functions and pseudorandom generators

paper_content:

One-way are those functions which are easy to compute, but hard to invert on a non-negligible fraction of instances. The existence of such functions with some additional assumptions was shown to be sufficient for generating perfect pseudorandom strings |Blum, Micali 82|, |Yao 82|, |Goldreich, Goldwasser, Micali 84|. Below, among a few other observations, a weaker assumption about one-way functions is suggested, which is not only sufficient, but also necessary for the existence of pseudorandom generators. The main theorem can be understood without reading the sections 3-6.
---
paper_title: Hardness vs. randomness

paper_content:

A simple construction for a pseudorandom bit generator is presented. It stretches 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, etc.), using an arbitrary function that is hard for C. This generator reveals an equivalence between the problems of proving lower bounds and the problem of generating good pseudorandom sequences. Combining this construction with other arguments, a number of consequences are obtained. >
---
paper_title: On yao’s XOR-lemma

paper_content:

A fundamental lemma of Yao states that computational weakunpredictability of Boolean predicates is amplified when the results of several independent instances are XOR together. We survey two known proofs of Yao's Lemma and present a third alternative proof. The third proof proceeds by first proving that a function constructed by concatenating the values of the original function on several independent instances is much more unpredictable, with respect to specified complexity bounds, than the original function. This statement turns out to be easier to prove than the XOR-Lemma. Using a result of Goldreich and Levin (1989) and some elementary observation, we derive the XOR-Lemma.
---
paper_title: Hiding instances in multioracle queries

paper_content:

Abadi, Feigenbaum, and Kilian have considered instance-hiding schemes [1]. Let f be a function for which no randomized polynomial-time algorithm is known; randomized polynomial-time machine A wants to query an oracle B for f to obtain f(x), without telling B exactly what x is. It is shown in [1] that, if f is an NP-hard function, A cannot query a single oracle B while hiding all but the size of the instance, assuming that the polynomial hierarchy does not collapse. This negative result holds for all oracles B, including those that are non-r.e.
---
paper_title: BPP has subexponential time simulations unless EXPTIME has publishable proofs

paper_content:

It is shown that BPP can be simulated in subexponential time for infinitely many input lengths unless exponential time collapses to the second level of the polynomial-time hierarchy, has polynomial-size circuits, and has publishable proofs (EXPTIME=MA). It is also shown that BPP is contained in subexponential time unless exponential time has publishable proofs for infinitely many input lengths. In addition, it is shown that BPP can be simulated in subexponential time for infinitely many input lengths unless there exist unary languages in MA/P. The proofs are based on the recent characterization of the power of multiprover interactive protocols and on random self-reducibility via low degree polynomials. They exhibit an interplay between Boolean circuit simulation, interactive proofs and classical complexity classes. An important feature of this proof is that it does not relativize.<<ETX>>
---
paper_title: Hard-core distributions for somewhat hard problems

paper_content:

Consider a decision problem that cannot be 1-/spl delta/ approximated by circuits of a given size in the sense that any such circuit fails to give the correct answer on at least a /spl delta/ fraction of instances. We show that for any such problem there is a specific "hard core" set of inputs which is at least a /spl delta/ fraction of all inputs and on which no circuit of a slightly smaller size can get even a small advantage over a random guess. More generally, our argument holds for any non uniform model of computation closed under majorities. We apply this result to get a new proof of the Yao XOR lemma (A.C. Yao, 1982), and to get a related XOR lemma for inputs that are only k wise independent.
---
paper_title: Hardness vs. randomness

paper_content:

A simple construction for a pseudorandom bit generator is presented. It stretches 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, etc.), using an arbitrary function that is hard for C. This generator reveals an equivalence between the problems of proving lower bounds and the problem of generating good pseudorandom sequences. Combining this construction with other arguments, a number of consequences are obtained. >
---
paper_title: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols

paper_content:

We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers convince a randomizing polynomial time verifier in polynomial time that the inputx belongs to the languageL. We show that the class of languages having tow-prover interactive proof systems is nondeterministic exponential time.We also show that to prove membership in languages inEXP, the honest provers need the power ofEXP only.The first part of the proof of the main result extends recent techniques of polynomial extrapolation used in the single prover case by Lund, Fortnow, Karloff, Nisan, and Shamir.The second part is averification scheme for multilinearity of a function in several variables held by an oracle and can be viewed as an independent result onprogram verification. Its proof rests on combinatorial techniques employing a simple isoperimetric inequality for certain graphs:
---
paper_title: Worst-Case Hardness Suffices for Derandomization: A New Method for Hardness-Randomness Trade-Offs

paper_content:

Up to know, the known derandomization methods have been derived assuming average-case hardness conditions. In this paper we instead present the first worst-case hardness conditions sufficient to obtain P=BPP.
---
paper_title: A new general derandomization method

paper_content:

We show that quick hitting set generators can replace quick pseudorandom generators to derandomize any probabilistic two-sided error algorithms. Up to now quick hitting set generators have been known as the general and uniform derandomization method for probabilistic one-sided error algorithms, while quick pseudorandom generators as the generators as the general and uniform method to derandomize probabilistic two-sided error algorithms. Our method is based on a deterministic algorithm that, given a Boolean circuit C and given access to a hitting set generator, constructs a discrepancy set for C . The main novelty is that the discrepancy set depends on C , so the new derandomization method is not uniform (i.e., not oblivious ). The algorithm works in time exponential in k(p(n)) where k (*) is the price of the hitting set generator and p (*) is a polynomial function in the size of C . We thus prove that if a logarithmic price quick hitting set generator exists then BPP = P.
---
paper_title: BPP has subexponential time simulations unless EXPTIME has publishable proofs

paper_content:

It is shown that BPP can be simulated in subexponential time for infinitely many input lengths unless exponential time collapses to the second level of the polynomial-time hierarchy, has polynomial-size circuits, and has publishable proofs (EXPTIME=MA). It is also shown that BPP is contained in subexponential time unless exponential time has publishable proofs for infinitely many input lengths. In addition, it is shown that BPP can be simulated in subexponential time for infinitely many input lengths unless there exist unary languages in MA/P. The proofs are based on the recent characterization of the power of multiprover interactive protocols and on random self-reducibility via low degree polynomials. They exhibit an interplay between Boolean circuit simulation, interactive proofs and classical complexity classes. An important feature of this proof is that it does not relativize.<<ETX>>
---
paper_title: Decoding of Reed Solomon codes beyond the error-correction bound

paper_content:

We present a randomized algorithm which takes as inputndistinct points {(xi,yi)}i= 1nfromF×F(whereFis a field) and integer parameterstanddand returns a list of all univariate polynomialsfoverFin the variablexof degree at mostdwhich agree with the given set of points in at leasttplaces (i.e.,yi=f(xi) for at leasttvalues ofi), providedt= ?(nd). The running time is bounded by a polynomial inn. This immediately provides a maximum likelihood decoding algorithm for Reed Solomon Codes, which works in a setting with a larger number of errors than any previously known algorithm. To the best of our knowledge, this is the first efficient (i.e., polynomial time bounded) algorithm which provides error recovery capability beyond the error-correction bound of a code for any efficient (i.e., constant or even polynomial rate) code.
---
paper_title: Improved low-degree testing and its applications

paper_content:

NP = PCP(logn, 1) and related results crucially depend upon the close connection between the probability with which a function passes a low degree test and the distance of this function to the nearest degree d polynomial. In this paper we study a test proposed by Rubinfeld and Sudan [30]. The strongest previously known connection for this test states that a function passes the test with probability δ for some δ > 7/8 iff the function has agreement ≈ δ with a polynomial of degree d. We present a new, and surprisingly strong, analysis which shows that the preceding statement is true for arbitrarily small δ, provided the field size is polynomially larger than d/δ. The analysis uses a version of Hilbert irreducibility, a tool of algebraic geometry. As a consequence we obtain an alternate construction for the following proof system: A constant prover 1-round proof system for NP languages in which the verifier uses O(logn) random bits, receives answers of size O(logn) bits, and has an error probability of at most 2− log 1− . Such a proof system, which implies the NP-hardness of approximating Set Cover to within Ω(logn) factors, has already been obtained by Raz and Safra [29]. Raz and Safra obtain their result by giving a strong analysis, in the sense described above, of a new low-degree test that they present. A second consequence of our analysis is a self tester/corrector for any buggy program that (supposedly) computes a polynomial over a finite field. If the program is correct only on δ fraction of inputs where δ = 1/ |F| 0.5, then the tester/corrector determines δ and generates O( 1 δ ) values for every input, such that one of them is the correct output. In fact, our results yield something stronger: Given the buggy program, we can construct O( 1 δ ) randomized programs such that one of them is correct on every input, with high probability. Such a strong selfcorrector is a useful tool in complexity theory with some applications known. ∗arora@cs.princeton.edu. Supported by an NSF CAREER award, an Alfred P. Sloan Fellowship, and a Packard Fellowship. †madhu@lcs.mit.edu. Laboratory for Computer Science, MIT, Cambridge, MA 02139. Part of this work was done when this author was at the IBM Thomas J. Watson Research Center.
---
paper_title: Pseudorandom generators without the XOR Lemma

paper_content:

Summary form only given. R. Impagliazzo and A. Wigderson (1997) have recently shown that if there exists a decision problem solvable in time 2/sup O(n)/ and having circuit complexity 2/sup /spl Omega/(n)/ (for all but finitely many n) then P=BPP. This result is a culmination of a series of works showing connections between the existence of hard predicates and the existence of good pseudorandom generators. The construction of Impagliazzo and Wigderson goes through three phases of "hardness amplification" (a multivariate polynomial encoding, a first derandomized XOR Lemma, and a second derandomized XOR Lemma) that are composed with the Nisan-Wigderson (1994) generator. In this paper we present two different approaches to proving the main result of Impagliazzo and Wigderson. In developing each approach, we introduce new techniques and prove new results that could be useful in future improvements and/or applications of hardness-randomness trade-offs.
---
paper_title: List decoding: algorithms and applications

paper_content:

Over the years coding theory and complexity theory have benefited from a number of mutually enriching connections. This article focuses on a new connection that has emerged between the two topics in the recent years. This connection is centered around the notion of “list-decoding” for error-correcting codes. In this survey we describe the list-decoding problem, the algorithms that have been developed, and a diverse collection of applications within complexity theory.
---
paper_title: Binary codes with specified minimum distance

paper_content:

Two n -digit sequences, called "points," of binary digits are said to be at distance d if exactly d corresponding digits are unlike in the two sequences. The construction of sets of points, called codes, in which some specified minimum distance is maintained between pairs of points is of interest in the design of self-checking systems for computing with or transmitting binary digits, the minimum distance being the minimum number of digital errors required to produce an undetected error in the system output. Previous work in the field had established general upper bounds for the number of n -digit points in codes of minimum distance d with certain properties. This paper gives new results in the field in the form of theorems which permit systematic construction of codes for given n, d ; for some n, d , the codes contain the greatest possible numbers of points.
---
paper_title: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses

paper_content:

We establish hardness versus randomness trade-offs for a broad class of randomized procedures. In particular, we create efficient nondeterministic simulations of bounded round Arthur-Merlin games using a language in exponential time that cannot be decided by polynomial size oracle circuits with access to satisfiability. We show that every language with a bounded round Arthur-Merlin game has subexponential size membership proofs for infinitely many input lengths unless the polynomial-time hierarchy collapses. This provides the first strong evidence that graph nonisomorphism has subexponential size proofs. We set up a general framework for derandomization which encompasses more than the traditional model of randomized computation. For a randomized procedure to fit within this framework, we only require that for any fixed input the complexity of checking whether the procedure succeeds on a given random bit sequence is not too high. We then apply our derandomization technique to four fundamental complexity theoretic constructions: The Valiant-Vazirani random hashing technique which prunes the number of satisfying assignments of a Boolean formula to one, and related procedures like computing satisfying assignments to Boolean formulas non-adaptively given access to an oracle for satisfiability. The algorithm of Bshouty et al. for learning Boolean circuits. Constructing matrices with high rigidity. Constructing polynomial-size universal traversal sequences. We also show that if linear space requires exponential size circuits, then space bounded randomized computations can be simulated deterministically with only a constant factor overhead in space.
---
paper_title: BPP has subexponential time simulations unless EXPTIME has publishable proofs

paper_content:

It is shown that BPP can be simulated in subexponential time for infinitely many input lengths unless exponential time collapses to the second level of the polynomial-time hierarchy, has polynomial-size circuits, and has publishable proofs (EXPTIME=MA). It is also shown that BPP is contained in subexponential time unless exponential time has publishable proofs for infinitely many input lengths. In addition, it is shown that BPP can be simulated in subexponential time for infinitely many input lengths unless there exist unary languages in MA/P. The proofs are based on the recent characterization of the power of multiprover interactive protocols and on random self-reducibility via low degree polynomials. They exhibit an interplay between Boolean circuit simulation, interactive proofs and classical complexity classes. An important feature of this proof is that it does not relativize.<<ETX>>
---
paper_title: Trading group theory for randomness

paper_content:

In a previous paper [BS] we proved, using the elements of the theory of nilpotent groups , that some of the fundamental computational problems in matriz groups belong to NP . These problems were also shown to belong to coNP , assuming an unproven hypothesis concerning finite simple groups . The aim of this paper is to replace most of the (proven and unproven) group theory of [BS] by elementary combinatorial arguments. The result we prove is that relative to a random oracle B , the mentioned matrix group problems belong to ( NP∩coNP ) B . The problems we consider are membership in and order of a matrix group given by a list of generators. These problems can be viewed as multidimensional versions of a close relative of the discrete logarithm problem. Hence NP∩coNP might be the lowest natural complexity class they may fit in. We remark that the results remain valid for black box groups where group operations are performed by an oracle. The tools we introduce seem interesting in their own right. We define a new hierarchy of complexity classes AM ( k ) “just above NP ”, introducing Arthur vs. Merlin games , the bounded-away version of Papdimitriou's Games against Nature . We prove that in spite of their analogy with the polynomial time hierarchy, the finite levels of this hierarchy collapse to AM=AM (2). Using a combinatorial lemma on finite groups [BE], we construct a game by which the nondeterministic player (Merlin) is able to convince the random player (Arthur) about the relation [ G ]= N provided Arthur trusts conclusions based on statistical evidence (such as a Slowly-Strassen type “proof” of primality). One can prove that AM consists precisely of those languages which belong to NP B for almost every oracle B . Our hierarchy has an interesting, still unclarified relation to another hierarchy, obtained by removing the central ingredient from the User vs. Expert games of Goldwasser, Micali and Rackoff.
---
paper_title: Near-optimal conversion of hardness into pseudo-randomness

paper_content:

Various efforts have been made to derandomize probabilistic algorithms using the assumption that there exists a problem in E=dtime(2/sup O(n)/) that requires circuits of size s(n) (for some function s). These results are based on the NW (Nisan & Wigderson, 1997) generator. For the strong lower bound s(n)=2/sup /spl epsi/n/, the optimal derandomization is P=BPP. However, for weaker lower bound functions s(n), these constructions fall short of the natural conjecture for optimal derandomization that bptime(t)/spl sube/ dtime(2?O[s/sup -1/(t)]). The gap is due to an inherent efficiency limitation in NW-style pseudorandom generators. We are able to obtain derandomization in almost optimal time using any lower bound s(n). We do this by using the NW-generator in a more sophisticated way. We view any failure of the generator as a reduction from the given hard function to its restrictions on smaller input sizes. Thus, either the original construction works optimally or one of the restricted functions is as hard as the original. Any such restriction can then be plugged into the NW-generator recursively. This process generates many candidate generators, and at least one is guaranteed to be good. To perform the approximation of the acceptance probability of the given circuit, we run a tournament between the candidate generators which yields an accurate estimate. We explore information theoretic analogs of our new construction. The inherent limitation of the NW-generator makes the extra randomness required by that extractor suboptimal. However, applying our construction, we get an almost optimal disperser.
---
paper_title: Simple extractors for all min-entropies and a new pseudorandom generator

paper_content:

A “randomness extractor” is an algorithm that given a sample from a distribution with sufficiently high min-entropy and a short random seed produces an output that is statistically indistinguishable from uniform. (Min-entropy is a measure of the amount of randomness in a distribution.) We present a simple, self-contained extractor construction that produces good extractors for all min-entropies. Our construction is algebraic and builds on a new polynomial-based approach introduced by Ta-Shma et al. [2001b]. Using our improvements, we obtain, for example, an extractor with output length m = k/(log n)O(1/α) and seed length (1 p α)log n for an arbitrary 0 < α ≤ 1, where n is the input length, and k is the min-entropy of the input distribution.A “pseudorandom generator” is an algorithm that given a short random seed produces a long output that is computationally indistinguishable from uniform. Our technique also gives a new way to construct pseudorandom generators from functions that require large circuits. Our pseudorandom generator construction is not based on the Nisan-Wigderson generator [Nisan and Wigderson 1994], and turns worst-case hardness directly into pseudorandomness. The parameters of our generator match those in Impagliazzo and Wigderson [1997] and Sudan et al. [2001] and in particular are strong enough to obtain a new proof that P = BPP if E requires exponential size circuits.Our construction also gives the following improvements over previous work:---We construct an optimal “hitting set generator” that stretches O(log n) random bits into sΩ(1) pseudorandom bits when given a function on log n bits that requires circuits of size s. This yields a quantitatively optimal hardness versus randomness tradeoff for both RP and BPP and solves an open problem raised in Impagliazzo et al. [1999].---We give the first construction of pseudorandom generators that fool nondeterministic circuits when given a function that requires large nondeterministic circuits. This technique also give a quantitatively optimal hardness versus randomness tradeoff for AM and the first hardness amplification result for nondeterministic circuits.
---
paper_title: A new general derandomization method

paper_content:

We show that quick hitting set generators can replace quick pseudorandom generators to derandomize any probabilistic two-sided error algorithms. Up to now quick hitting set generators have been known as the general and uniform derandomization method for probabilistic one-sided error algorithms, while quick pseudorandom generators as the generators as the general and uniform method to derandomize probabilistic two-sided error algorithms. Our method is based on a deterministic algorithm that, given a Boolean circuit C and given access to a hitting set generator, constructs a discrepancy set for C . The main novelty is that the discrepancy set depends on C , so the new derandomization method is not uniform (i.e., not oblivious ). The algorithm works in time exponential in k(p(n)) where k (*) is the price of the hitting set generator and p (*) is a polynomial function in the size of C . We thus prove that if a logarithmic price quick hitting set generator exists then BPP = P.
---
paper_title: Another proof that BPP ⊆ PH (and more

paper_content:

We provide another proof of the Sipser-Lautemann Theorem by which BPP ⊆ MA (⊆ PH). The current proof is based on strong results regarding the amplification of BPP, due to Zuckerman (1996). Given these results, the current proof is even simpler than previous ones. Furthermore, extending the proof leads to two results regarding MA: MA ⊆ ZPPNP (which seems to be new), and that two-sided error MA equals MA. Finally, we survey the known facts regarding the fragment of the polynomial-time hierarchy that contains MA.
---
paper_title: NP is as easy as detecting unique solutions

paper_content:

Abstract For every known NP-complete problem, the number of solutions of its instances varies over a large range, from zero to exponentially many. It is therefore natural to ask if the inherent intractability of NP-complete problem is caused by this wide variation. We give a negative answer to this question using the notion of randomized polynomial time reducibility. We show that the problems of distinguishing between instances of SAT having zero or one solution, or of finding solutions to instances of SAT having a unique solution, are as hard as SAT, under randomized reductions. Several corollaries about the difficulty of specific problems follow. For example, computing the parity of the number of solutions of a SAT formula is shown to be NP-hard, and deciding if a SAT formula has a unique solution is shown to be D p -hard, under randomized reduction. Central to the study of cryptography is the question as to whether there exist NP-problems whose instances have solutions that are unique but are hard to find. Our result can be interpreted as strengthening the belief that such problems exist.
---
paper_title: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses

paper_content:

We establish hardness versus randomness trade-offs for a broad class of randomized procedures. In particular, we create efficient nondeterministic simulations of bounded round Arthur-Merlin games using a language in exponential time that cannot be decided by polynomial size oracle circuits with access to satisfiability. We show that every language with a bounded round Arthur-Merlin game has subexponential size membership proofs for infinitely many input lengths unless the polynomial-time hierarchy collapses. This provides the first strong evidence that graph nonisomorphism has subexponential size proofs. We set up a general framework for derandomization which encompasses more than the traditional model of randomized computation. For a randomized procedure to fit within this framework, we only require that for any fixed input the complexity of checking whether the procedure succeeds on a given random bit sequence is not too high. We then apply our derandomization technique to four fundamental complexity theoretic constructions: The Valiant-Vazirani random hashing technique which prunes the number of satisfying assignments of a Boolean formula to one, and related procedures like computing satisfying assignments to Boolean formulas non-adaptively given access to an oracle for satisfiability. The algorithm of Bshouty et al. for learning Boolean circuits. Constructing matrices with high rigidity. Constructing polynomial-size universal traversal sequences. We also show that if linear space requires exponential size circuits, then space bounded randomized computations can be simulated deterministically with only a constant factor overhead in space.
---
paper_title: Simple extractors for all min-entropies and a new pseudorandom generator

paper_content:

A “randomness extractor” is an algorithm that given a sample from a distribution with sufficiently high min-entropy and a short random seed produces an output that is statistically indistinguishable from uniform. (Min-entropy is a measure of the amount of randomness in a distribution.) We present a simple, self-contained extractor construction that produces good extractors for all min-entropies. Our construction is algebraic and builds on a new polynomial-based approach introduced by Ta-Shma et al. [2001b]. Using our improvements, we obtain, for example, an extractor with output length m = k/(log n)O(1/α) and seed length (1 p α)log n for an arbitrary 0 < α ≤ 1, where n is the input length, and k is the min-entropy of the input distribution.A “pseudorandom generator” is an algorithm that given a short random seed produces a long output that is computationally indistinguishable from uniform. Our technique also gives a new way to construct pseudorandom generators from functions that require large circuits. Our pseudorandom generator construction is not based on the Nisan-Wigderson generator [Nisan and Wigderson 1994], and turns worst-case hardness directly into pseudorandomness. The parameters of our generator match those in Impagliazzo and Wigderson [1997] and Sudan et al. [2001] and in particular are strong enough to obtain a new proof that P = BPP if E requires exponential size circuits.Our construction also gives the following improvements over previous work:---We construct an optimal “hitting set generator” that stretches O(log n) random bits into sΩ(1) pseudorandom bits when given a function on log n bits that requires circuits of size s. This yields a quantitatively optimal hardness versus randomness tradeoff for both RP and BPP and solves an open problem raised in Impagliazzo et al. [1999].---We give the first construction of pseudorandom generators that fool nondeterministic circuits when given a function that requires large nondeterministic circuits. This technique also give a quantitatively optimal hardness versus randomness tradeoff for AM and the first hardness amplification result for nondeterministic circuits.
---
paper_title: Derandomizing Arthur–Merlin Games using Hitting Sets

paper_content:

We prove that AM (and hence Graph Nonisomorphism) is in NP if for some e > 0, some language in NE ∩ coNE requires nondeterministic circuits of size 2en. This improves results of Arvind and Kobler and of Klivans and van Melkebeek who proved the same conclusion, but under stronger hardness assumptions.The previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim's hitting set approach to derandomization. As a spin-off, we show that this approach is strong enough to give an easy proof of the following implication: for some e > 0, if there is a language in E which requires nondeterministic circuits of size 2en, then P = BPP. This differs from Impagliazzo and Wigderson's theorem "only" by replacing deterministic circuits with nondeterministic ones.
---
paper_title: Extractors from Reed-Muller codes

paper_content:

Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. Previous research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, researchers had failed to build extractors directly from a good code without using other tools from pseudorandomness. We succeed in constructing an extractor directly from a Reed-Muller code. To do this, we develop a novel proof technique. Furthermore, our construction is the first to achieve a degree close to linear. In contrast, the best previous constructions brought the log of the degree within a constant of optimal, which gives polynomial degree. This improvement is important for certain applications. For example, it follows that approximating the VC dimension to within a factor of N/sup 1-/spl delta// is AM-hard for any positive /spl delta/.
---
paper_title: Simple extractors for all min-entropies and a new pseudorandom generator

paper_content:

A “randomness extractor” is an algorithm that given a sample from a distribution with sufficiently high min-entropy and a short random seed produces an output that is statistically indistinguishable from uniform. (Min-entropy is a measure of the amount of randomness in a distribution.) We present a simple, self-contained extractor construction that produces good extractors for all min-entropies. Our construction is algebraic and builds on a new polynomial-based approach introduced by Ta-Shma et al. [2001b]. Using our improvements, we obtain, for example, an extractor with output length m = k/(log n)O(1/α) and seed length (1 p α)log n for an arbitrary 0 < α ≤ 1, where n is the input length, and k is the min-entropy of the input distribution.A “pseudorandom generator” is an algorithm that given a short random seed produces a long output that is computationally indistinguishable from uniform. Our technique also gives a new way to construct pseudorandom generators from functions that require large circuits. Our pseudorandom generator construction is not based on the Nisan-Wigderson generator [Nisan and Wigderson 1994], and turns worst-case hardness directly into pseudorandomness. The parameters of our generator match those in Impagliazzo and Wigderson [1997] and Sudan et al. [2001] and in particular are strong enough to obtain a new proof that P = BPP if E requires exponential size circuits.Our construction also gives the following improvements over previous work:---We construct an optimal “hitting set generator” that stretches O(log n) random bits into sΩ(1) pseudorandom bits when given a function on log n bits that requires circuits of size s. This yields a quantitatively optimal hardness versus randomness tradeoff for both RP and BPP and solves an open problem raised in Impagliazzo et al. [1999].---We give the first construction of pseudorandom generators that fool nondeterministic circuits when given a function that requires large nondeterministic circuits. This technique also give a quantitatively optimal hardness versus randomness tradeoff for AM and the first hardness amplification result for nondeterministic circuits.
---
paper_title: Randomness vs. time: de-randomization under a uniform assumption

paper_content:

We prove that if BPP/spl ne/EXP, then every problem in BPP can be solved deterministically in subexponential time on almost every input (on every samplable ensemble for infinitely many input sizes). This is the first derandomization result for BPP based on uniform, noncryptographic hardness assumptions. It implies the following gap in the average-instance complexities of problems in BPP: either these complexities are always sub-exponential or they contain arbitrarily large exponential functions. We use a construction of a small "pseudorandom" set of strings from a "hard function" in EXP which is identical to that used in the analogous non-uniform results described previously. However, previous proofs of correctness assume the "hard function" is not in P/poly. They give a non-constructive argument that a circuit distinguishing the pseudo-random strings from truly random strings implies that a similarly-sized circuit exists computing the "hard function". Our main technical contribution is to show that, if the "hard function" has certain properties, then this argument can be made constructive. We then show that, assuming ESP/spl sube/P/poly, there are EXP-complete functions with these properties.
---
paper_title: The complexity of computing the permanent

paper_content:

Abstract It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations. Related counting problems are also considered. The reductions used are characterized by their nontrivial use of arithmetic.
---
paper_title: BPP has subexponential time simulations unless EXPTIME has publishable proofs

paper_content:

It is shown that BPP can be simulated in subexponential time for infinitely many input lengths unless exponential time collapses to the second level of the polynomial-time hierarchy, has polynomial-size circuits, and has publishable proofs (EXPTIME=MA). It is also shown that BPP is contained in subexponential time unless exponential time has publishable proofs for infinitely many input lengths. In addition, it is shown that BPP can be simulated in subexponential time for infinitely many input lengths unless there exist unary languages in MA/P. The proofs are based on the recent characterization of the power of multiprover interactive protocols and on random self-reducibility via low degree polynomials. They exhibit an interplay between Boolean circuit simulation, interactive proofs and classical complexity classes. An important feature of this proof is that it does not relativize.<<ETX>>
---
paper_title: PP IS AS HARD AS THE POLYNOMIAL-TIME HIERARCHY*

paper_content:

In this paper, two interesting complexity classes, PP and $ \oplus {\text{P}}$, are compared with PH, the polynomial-time hierarchy. It is shown that every set in PH is polynomial-time Turing reducible to a set in PP, and PH is included in ${\text{BP}} \cdot \oplus {\text{P}}$. As a consequence of the results, it follows that ${\text{PP}} \subseteq {\text{PH}}$ (or $\oplus {\text{P}} \subseteq {\text{PH}}$) implies a collapse of PH. A stronger result is also shown: every set in PP(PH) is polynomial-time Turing reducible to a set in PP.
---
paper_title: Algebraic methods for interactive proof systems

paper_content:

A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP = NEXP [4].
---
paper_title: The complexity of computing the permanent

paper_content:

Abstract It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations. Related counting problems are also considered. The reductions used are characterized by their nontrivial use of arithmetic.
---
paper_title: Pseudorandomness and average-case complexity via uniform reductions

paper_content:

Impagliazzo and Wigderson (1998) gave the first construction of pseudorandom generators from a uniform complexity assumption on EXP (namely EXP = BPP). Unlike results in the nonuniform setting, their result does not provide a continuous trade-off between worst-case hardness and pseudorandomness, nor does it explicitly establish an average-case hardness result. We obtain an optimal worst-case to average-case connection for EXP: if EXP BPTIME(( )), EXP has problems that are cannot be solved on a fraction 1/2 1/'( ) of the inputs by BPTIME('( )) algorithms, for ' = /sup 1/. We exhibit a PSPACE-complete downward self-reducible and random self-reducible problem. This slightly simplifies and strengthens the proof of Impagliazzo and Wigderson (1998), which used a a P-complete problem with these properties. We argue that the results in Impagliazzo and Wigderson (1998) and in this paper cannot be proved via "black-box" uniform reductions.
---
paper_title: PP IS AS HARD AS THE POLYNOMIAL-TIME HIERARCHY*

paper_content:

In this paper, two interesting complexity classes, PP and $ \oplus {\text{P}}$, are compared with PH, the polynomial-time hierarchy. It is shown that every set in PH is polynomial-time Turing reducible to a set in PP, and PH is included in ${\text{BP}} \cdot \oplus {\text{P}}$. As a consequence of the results, it follows that ${\text{PP}} \subseteq {\text{PH}}$ (or $\oplus {\text{P}} \subseteq {\text{PH}}$) implies a collapse of PH. A stronger result is also shown: every set in PP(PH) is polynomial-time Turing reducible to a set in PP.
---
paper_title: Pseudorandom generators without the XOR Lemma

paper_content:

Summary form only given. R. Impagliazzo and A. Wigderson (1997) have recently shown that if there exists a decision problem solvable in time 2/sup O(n)/ and having circuit complexity 2/sup /spl Omega/(n)/ (for all but finitely many n) then P=BPP. This result is a culmination of a series of works showing connections between the existence of hard predicates and the existence of good pseudorandom generators. The construction of Impagliazzo and Wigderson goes through three phases of "hardness amplification" (a multivariate polynomial encoding, a first derandomized XOR Lemma, and a second derandomized XOR Lemma) that are composed with the Nisan-Wigderson (1994) generator. In this paper we present two different approaches to proving the main result of Impagliazzo and Wigderson. In developing each approach, we introduce new techniques and prove new results that could be useful in future improvements and/or applications of hardness-randomness trade-offs.
---
paper_title: Derandomizing Arthur-Merlin Games under Uniform Assumptions

paper_content:

We study how the nondeterminism versus determinism problem and the time versus space problem are related to the problem of derandomization. In particular, we show two ways of derandomizing the complexity class AM under uniform assumptions, which was only known previously under non-uniform assumptions [13,14]. First, we prove that either AM = NP or it appears to any nondeterministic polynomial time adversary that NP is contained in deterministic subexponential time infinitely often. This implies that to any nondeterministic polynomial time adversary, the graph non-isomorphism problem appears to have subexponential-size proofs infinitely often, the first nontrivial derandomization of this problem without any assumption. Next, we show that either all BPP = P, AM = NP, and PH ⊆ ⊕P hold, or for any t(n) = 2Ω(n), DTIME(t(n)) ⊆ DSPACE(tƐ(n)) infinitely often for any constant Ɛ > 0. Similar tradeoffs also hold for a whole range of parameters. This improves previous results [17,5] and seems to be the first example of an interesting condition that implies three derandomiztion results at once.
---
paper_title: Efficiently Approximable Real-Valued Functions

paper_content:

We define a class, denoted APP, of real-valued functions f : {0, 1}n → [0, 1] such that f can be approximated to within any > 0 by a probabilistic Turing machine running in time poly(n, 1/ ). The class APP can be viewed as a generalization of BPP. We argue that APP is more natural and more important than BPP, and that most results about BPP are better stated as results about APP. We show that APP contains a natural complete problem: computing the acceptance probability of a given Boolean circuit. In contrast, no complete problem is known for BPP. We observe that all known complexity-theoretic assumptions under which BPP can be derandomized also allow APP to be derandomized. On the other hand we construct an oracle under which BPP = P but APP does not collapse to the corresponding deterministic class AP. (However any oracle collapsing APP to AP also collapses BPP to P.)
---
paper_title: Comparing notions of full derandomization

paper_content:

Most of the hypotheses of full derandomization fall into two sets of equivalent statements: those equivalent to the existence of efficient pseudorandom generators and those equivalent to approximating the accepting probability of a circuit. We give the first relativized world where these sets of equivalent statements are not equivalent to each other.
---
paper_title: In search of an easy witness: exponential time vs. probabilistic polynomial time

paper_content:

Restricting the search space (0, l}” to the set of truth tables of “easy” Boolean functions on log 1% variables, as well as using some known hardness-randomness tradeoff., we establish a number of results relating the complexi@ of exponential-time and probabilistic polynomial-time coniplexity classes. In particular; we show that NEXP C P/poly e NEXP = MA; this can be interpreted to say that no derandomization of MA (and, hence, of promise- BPP) is possible unless N EXP contains a hard Boolean function. We also prove several downward closure results for ZPP, RP, BPP, and MA; e.g., we show EXP = BPP EE = BPE, where EE is the double-exponential time class and BPE is the exponential-time analogue of BPP.
---
paper_title: Derandomizing Arthur–Merlin Games using Hitting Sets

paper_content:

We prove that AM (and hence Graph Nonisomorphism) is in NP if for some e > 0, some language in NE ∩ coNE requires nondeterministic circuits of size 2en. This improves results of Arvind and Kobler and of Klivans and van Melkebeek who proved the same conclusion, but under stronger hardness assumptions.The previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim's hitting set approach to derandomization. As a spin-off, we show that this approach is strong enough to give an easy proof of the following implication: for some e > 0, if there is a language in E which requires nondeterministic circuits of size 2en, then P = BPP. This differs from Impagliazzo and Wigderson's theorem "only" by replacing deterministic circuits with nondeterministic ones.
---
paper_title: Nonrelativizing separations

paper_content:

We show that MA/sub EXP/, the exponential time version of the Merlin-Arthur class, does not have polynomial size circuits. This significantly improves the previous known result due to Kannan since we furthermore show that our result does not relativize. This is the first separation result in complexity theory that does not relativize. As a corollary to our separation result we also obtain that PEXP, the exponential time version of PP is nor in P/poly.
---
paper_title: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols

paper_content:

We determine the exact power of two-prover interactive proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers convince a randomizing polynomial time verifier in polynomial time that the inputx belongs to the languageL. We show that the class of languages having tow-prover interactive proof systems is nondeterministic exponential time.We also show that to prove membership in languages inEXP, the honest provers need the power ofEXP only.The first part of the proof of the main result extends recent techniques of polynomial extrapolation used in the single prover case by Lund, Fortnow, Karloff, Nisan, and Shamir.The second part is averification scheme for multilinearity of a function in several variables held by an oracle and can be viewed as an independent result onprogram verification. Its proof rests on combinatorial techniques employing a simple isoperimetric inequality for certain graphs:
---
paper_title: Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

paper_content:

We show that derandomizing Polynomial Identity Testing is essentially equivalent to proving arithmetic circuit lower bounds for NEXP. More precisely, we prove that if one can test in polynomial time (or even nondeterministic subexponential time, infinitely often) whether a given arithmetic circuit over integers computes an identically zero polynomial, then either (i) NEXP ⊄ P/poly or (ii) Permanent is not computable by polynomial-size arithmetic circuits. We also prove a (partial) converse: If Permanent requires superpolynomial-size arithmetic circuits, then one can test in subexponential time whether a given arithmetic circuit of polynomially bounded degree computes an identically zero polynomial.Since Polynomial Identity Testing is a coRP problem, we obtain the following corollary: If RP = P (or even coRP ⊆ ∩e > 0 NTIME(2ne), infinitely often), then NEXP is not computable by polynomial-size arithmetic circuits. Thus establishing that RP = coRP or BPP = P would require proving superpolynomial lower bounds for Boolean or arithmetic circuits. We also show that any derandomization of RNC would yield new circuit lower bounds for a language in NEXP.We also prove unconditionally that NEXPRP does not have polynomial-size Boolean or arithmetic circuits. Finally, we show that NEXP ⊄ P/poly if both BPP = P and low-degree testing is in P; here low-degree testing is the problem of checking whether a given Boolean circuit computes a function that is close to some low-degree polynomial over a finite field.
---
paper_title: The complexity of computing the permanent

paper_content:

Abstract It is shown that the permanent function of (0, 1)-matrices is a complete problem for the class of counting problems associated with nondeterministic polynomial time computations. Related counting problems are also considered. The reductions used are characterized by their nontrivial use of arithmetic.
---
paper_title: PP IS AS HARD AS THE POLYNOMIAL-TIME HIERARCHY*

paper_content:

In this paper, two interesting complexity classes, PP and $ \oplus {\text{P}}$, are compared with PH, the polynomial-time hierarchy. It is shown that every set in PH is polynomial-time Turing reducible to a set in PP, and PH is included in ${\text{BP}} \cdot \oplus {\text{P}}$. As a consequence of the results, it follows that ${\text{PP}} \subseteq {\text{PH}}$ (or $\oplus {\text{P}} \subseteq {\text{PH}}$) implies a collapse of PH. A stronger result is also shown: every set in PP(PH) is polynomial-time Turing reducible to a set in PP.
---
paper_title: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses

paper_content:

We establish hardness versus randomness trade-offs for a broad class of randomized procedures. In particular, we create efficient nondeterministic simulations of bounded round Arthur-Merlin games using a language in exponential time that cannot be decided by polynomial size oracle circuits with access to satisfiability. We show that every language with a bounded round Arthur-Merlin game has subexponential size membership proofs for infinitely many input lengths unless the polynomial-time hierarchy collapses. This provides the first strong evidence that graph nonisomorphism has subexponential size proofs. We set up a general framework for derandomization which encompasses more than the traditional model of randomized computation. For a randomized procedure to fit within this framework, we only require that for any fixed input the complexity of checking whether the procedure succeeds on a given random bit sequence is not too high. We then apply our derandomization technique to four fundamental complexity theoretic constructions: The Valiant-Vazirani random hashing technique which prunes the number of satisfying assignments of a Boolean formula to one, and related procedures like computing satisfying assignments to Boolean formulas non-adaptively given access to an oracle for satisfiability. The algorithm of Bshouty et al. for learning Boolean circuits. Constructing matrices with high rigidity. Constructing polynomial-size universal traversal sequences. We also show that if linear space requires exponential size circuits, then space bounded randomized computations can be simulated deterministically with only a constant factor overhead in space.
---

Title: Derandomization: a brief overview

Section 1: History
Description 1: Provide a historical context and background on derandomization, including the emergence and significance of randomized algorithms and the belief that BPP may be equal to P.

Section 2: Hardness-randomness tradeoffs
Description 2: Discuss the core concept of trading computational hardness for randomness and the fundamental results and examples supporting this idea.

Section 3: The Nisan-Wigderson generator
Description 3: Explain the significance of the NW generator, its construction, and how it improves upon previous results by using hardness assumptions.

Section 4: Worst-case hardness-randomness tradeoffs
Description 4: Detail the advancements in derandomization achieved through focusing on worst-case hardness and its implications for proving BPP = P.

Section 5: Hitting-set generators
Description 5: Describe the concept of hitting-set generators, their construction, and their role in achieving derandomization results.

Section 6: Recent developments
Description 6: Summarize recent advances in derandomization research, including improvements in hardness-randomness tradeoffs and new applications.

Section 7: Achieving optimal hardness-randomness tradeoffs
Description 7: Discuss what constitutes an optimal hardness-randomness tradeoff and recent results that approach or achieve these optimal tradeoffs.

Section 8: Beyond computational complexity
Description 8: Explore the implications and applications of hardness-randomness tradeoffs beyond the realm of computational complexity, such as in information theory.

Section 9: Back to computational complexity
Description 9: Examine how insights from the information-theoretic setting can be used to improve computational complexity results, particularly in constructing extractors.

Section 10: Derandomizing BPP
Description 10: Provide an in-depth look at the methods and results for derandomizing the class BPP, including both non-uniform and uniform hardness assumptions.

Section 11: Derandomizing RP
Description 11: Discuss techniques specific to derandomizing the class RP, along with relevant results and their proofs.

Section 12: Derandomizing AM
Description 12: Detail the challenges and results related to derandomizing the class AM, including significant theorems and their implications.

Section 13: Circuit lower bounds from the derandomization of MA
Description 13: Investigate the connection between derandomization of MA and circuit lower bounds, including key results and their proofs.

Section 14: Circuit lower bounds from the derandomization of BPP
Description 14: Explore recent findings that link derandomizing BPP to proving circuit lower bounds for classes like NEXP and the Permanent function.

Section 15: Other Results
Description 15: Highlight additional results and advancements in derandomization and complexity theory, covering a variety of topics and open questions.

Section 16: What Next?
Description 16: Discuss open problems and future directions in derandomization research, with a focus on extending current results and addressing unresolved questions.