David Zuckerman

STOC Conference 2025 Conference Paper

Linear Hashing Is Optimal

• Michael Jaber
• Vinayak M. Kumar
• David Zuckerman

We prove that hashing n balls into n bins via random 2 -linear maps yields expected maximum load O (log n / loglog n ), resolving an open question of Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos (STOC ’97, JACM ’99). More generally, we show that the maximum load exceeds r · log n /loglog n with probability at most O (1/ r 2 ). Our proof uses potential functions to detect heavy bins.

FOCS Conference 2024 Conference Paper

Improved Condensers for Chor-Goldreich Sources

• Jesse Goodman
• Xin Li 0006
• David Zuckerman

One of the earliest models of weak randomness is the Chor-Goldreich (CG) source. A $(t, n, k)\text{-}$ CG source is a sequence of random variables X $=(\mathrm{x}_{1}, \ldots, \mathrm{x}_{t})\sim(\{0, 1\}^{n})^{t}$, where each $\mathrm{X}_{i}$ has min-entropy $k$ conditioned on any fixing of $\mathrm{x}_{1}, \ldots, \mathrm{x}_{i-1}$. Chor and Goldreich proved that there is no deterministic way to extract randomness from such a source. Nevertheless, Doron, Moshkovitz, Oh, and Zuckerman showed that there is a deterministic way to condense a CG source into a string with small entropy gap. They gave applications of such a condenser to simulating randomized algorithms with small error and to certain cryptographic tasks. They studied the case where the block length $n$ and entropy rate $k/n$ are both constant. We study the much more general setting where the block length can be arbitrarily large, and the entropy rate can be arbitrarily small. We construct the first explicit condenser for CG sources in this setting, and it can be instantiated in a number of different ways. When the entropy rate of the CG source is constant, our condenser requires just a constant number of blocks $t$ to produce an output with entropy rate 0. 9, say. In the low entropy regime, using $t= \text{poly} (n)$ blocks, our condenser can achieve output entropy rate 0. 9 even if each block has just 1 bit of min-entropy. Moreover, these condensers have exponentially small error. Finally, we provide strong existential and impossibility results. For our existential result, we show that a random function is a seedless condenser (with surprisingly strong parameters) for any small family of sources. As a corollary, we get new existential results for seeded condensers and condensers for CG sources. For our impossibility result, we show the latter result is nearly tight, by giving a simple proof that the output of any condenser for CG sources must inherit the entropy gap of (one block of) its input.

STOC Conference 2023 Conference Paper

Almost Chor-Goldreich Sources and Adversarial Random Walks

• Dean Doron
• Dana Moshkovitz
• Justin Oh
• David Zuckerman

A Chor–Goldreich (CG) source is a sequence of random variables X = X 1 ∘ … ∘ X t , where each X i ∼ {0,1} d and X i has δ d min-entropy conditioned on any fixing of X 1 ∘ … ∘ X i −1 . The parameter 0<δ≤ 1 is the entropy rate of the source. We typically think of d as constant and t as growing. We extend this notion in several ways, defining almost CG sources. Most notably, we allow each X i to only have conditional Shannon entropy δ d . We achieve pseudorandomness results for almost CG sources which were not known to hold even for standard CG sources, and even for the weaker model of Santha–Vazirani sources: We construct a deterministic condenser that on input X , outputs a distribution which is close to having constant entropy gap, namely a distribution Z ∼ {0,1} m for m ≈ δ dt with min-entropy m − O (1). Therefore, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a “one-shot” simulation is needed. Moreover, our construction works in an online manner, since it is based on random walks on expanders. Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to X 1 ∘ … ∘ X t , accumulate most of the entropy in X .

STOC Conference 2023 Conference Paper

Extractors for Images of Varieties

• Zeyu Guo 0001
• Ben Lee Volk
• Akhil Jalan
• David Zuckerman

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map f : F q r → F q n to an element sampled uniformly at random from a k -dimensional variety V ⊆ F q r . This class of sources generalizes both polynomial sources, studied by Dvir, Gabizon and Wigderson (FOCS 2007, Comput. Complex. 2009), and variety sources, studied by Dvir (CCC 2009, Comput. Complex. 2012).

FOCS Conference 2020 Conference Paper

Extractors and Secret Sharing Against Bounded Collusion Protocols

• Eshan Chattopadhyay
• Jesse Goodman
• Vipul Goyal
• Ashutosh Kumar 0002
• Xin Li 0006
• Raghu Meka
• David Zuckerman

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs). BCPs are multiparty communication protocols in which N parties, holding n bits each, attempt to compute some joint function of their inputs, f: ({0, 1} n ) N →{0, 1}. In each round, p parties (the collusion bound) work together to write a single bit on a public blackboard, and the protocol continues until every party knows the value of f. BCPs are a natural generalization of the well-studied number-in-hand (NIH) and number-on-forehead (NOF) models, which are just endpoints on this rich spectrum of protocols (corresponding to p=1 and p=N-1, respectively). In this work, we investigate BCPs more thoroughly, and answer questions about them in the context of communication complexity, randomness extractors, and secret sharing. 1. First, we provide explicit lower bounds against BCPs. Our lower bounds offer a tradeoff between collusion and complexity, and are of the form n Ω(1) when p=0. 99N parties collude. This bound is independent of the relationship between N, n, whereas all previous bounds became trivial when. 2. Second, we provide explicit leakage-resilient extractors against BCPs. Also known as cylinder-intersection extractors, these objects are multi-source extractors of the form Ext: ({0, 1} n ) N →{0, 1}, whose output looks uniform even conditioned on the bits produced (“leaked”) by a BCP executed over the inputs of the extractor. Our extractors work for sources with min-entropy k ≥ polylog(n) against BCPs with collusion p ≤ N-2. Previously, all such extractors required min-entropy k ≥ 0. 99n even when p ≤ O(1). 3. Third, we provide efficient leakage-resilient secret sharing schemes against BCPs. These cryptographic primitives are standard t-out-of- N secret sharing schemes, equipped with an additional guarantee that the secret remains hidden even if the individuals participate in a BCP using their shares. Our schemes can handle collusion up to p ≤ O(t/logt), whereas the previous best scheme required p ≤ O(logN). Along the way, we also construct objects that are more general than those listed above (i. e. , compilers), objects that are more specialized (and stronger) than those listed above, and resolve open questions posed by Goyal and Kumar (STOC 2018) and Kumar, Meka, and Sahai (FOCS 2019).

FOCS Conference 2020 Conference Paper

Nearly Optimal Pseudorandomness From Hardness

• Dean Doron
• Dana Moshkovitz
• Justin Oh
• David Zuckerman

Existing proofs that deduce BPP = P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against randomized single-valued nondeterministic (SVN) circuits, we convert any randomized algorithm over inputs of length n running in time t ≥ n to a deterministic one running in time t 2+α for an arbitrarily small constant. Such a slowdown is nearly optimal, as, under complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that errs rarely into a deterministic algorithm having a similar running time (with pre-processing). The latter derandomization result holds under weaker assumptions, of exponential lower bounds against deterministic SVN circuits. Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1 + α)log s, under the assumption that there exists a function f ϵ E that requires randomized SVN circuits of size at least 2 (1-α')n, where. α=O(α'). The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.

STOC Conference 2020 Conference Paper

XOR lemmas for resilient functions against polynomials

• Eshan Chattopadhyay
• Pooya Hatami
• Kaave Hosseini
• Shachar Lovett
• David Zuckerman

A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over F 2 . We introduce a new technique to prove such correlation bounds with F 2 polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In fact, we prove a more general XOR lemma that extends to arbitrary resilient functions. We conjecture that the technique generalizes to higher degree polynomials as well. A key ingredient in our new approach is a structural result about the Fourier spectrum of low degree polynomials over F 2 . We show that for any n -variate polynomial p over F 2 of degree at most d , there is a small set S ⊂ [ n ] of variables, such that almost all of the Fourier mass of p lies on Fourier coefficients that intersect with S . In fact our result is more general, and finds such a set S for any low-dimensional subspace of polynomials. This generality is crucial in deriving the new XOR lemmas.

FOCS Conference 2018 Conference Paper

Simple Optimal Hitting Sets for Small-Success RL

• William M. Hoza
• David Zuckerman

We give a simple explicit hitting set generator for read-once branching programs of width w and length r with known variable order. When r = w, our generator has seed length O(log^2 r + log(1/ε)). When r = polylog w, our generator has optimal seed length O(log w + log(1/ε)). For intermediate values of r, our generator's seed length smoothly interpolates between these two extremes. Our generator's seed length improves on recent work by Braverman, Cohen, and Garg (STOC '18). In addition, our generator and its analysis are dramatically simpler than the work by Braverman et al. Our generator's seed length improves on all the classic generators for space-bounded computation (Nisan Combinatorica '92; Impagliazzo, Nisan, and Wigderson STOC '94; Nisan and Zuckerman JCSS '96) when eps is small. As a corollary of our construction, we show that every RL algorithm that uses r random bits can be simulated by an NL algorithm that uses only O(r/log^c n) nondeterministic bits, where c is an arbitrarily large constant. Finally, we show that any RL algorithm with small success probability eps can be simulated deterministically in space O(log^3/2 n + log n log log(1/ε)). This improves on work by Saks and Zhou (JCSS '99), who gave an algorithm that runs in space O(log^3/2 n + sqrt(log n) log(1/ε)).

STOC Conference 2016 Conference Paper

Explicit two-source extractors and resilient functions

• Eshan Chattopadhyay
• David Zuckerman

We explicitly construct an extractor for two independent sources on n bits, each with polylogarithmic min-entropy. Our extractor outputs one bit and has polynomially small error. The best previous extractor, by Bourgain, required each source to have min-entropy .499n. A key ingredient in our construction is an explicit construction of a monotone, almost-balanced Boolean functions that are resilient to coalitions. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylogarithmic-wise independently, and the remaining q bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q quadratically smaller than our result. Our explicit two-source extractor directly implies improved constructions of a K-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.

FOCS Conference 2016 Conference Paper

Robust Fourier and Polynomial Curve Fitting

• Venkatesan Guruswami
• David Zuckerman

We consider the robust curve fitting problem, for both algebraic and Fourier (trigonometric) polynomials, in the presence of outliers. In particular, we study the model of Arora and Khot (STOC 2002), who were motivated by applications in computer vision. In their model, the input data consists of ordered pairs (x i, y i ) ε [-1, 1] × [-1, 1], i = 1, 2, .. ., N, and there is an unknown degree-d polynomial p such that for all but ρ fraction of the i, we have |p(x i ) - y i |≤ δ. Unlike Arora-Khot, we also study the trigonometric setting, where the input is from T × [-1, 1], where T is the unit circle. In both scenarios, the i corresponding to errors are chosen randomly, and for such i the errors in the yi can be arbitrary. The goal is to output a degree-d polynomial q such that ||p - q|| ∞ is small (for example, O(δ)). Arora and Khot could achieve a polynomial-time algorithm only for ρ = 0. Daltrophe et al. observed that a simple median-based algorithm can correct errors if the desired accuracy δ is large enough. (Larger δ makes the output guarantee easier to achieve, which seems to typically outweigh the weaker input promise.) We dramatically expand the range of parameters for which recovery of q is possible in polynomial time. Specifically, we show that there are polynomial-time algorithms in both settings that recover q up to l∞ error O(δ. 99) provided 1) ρ ≤/c1log d and δ ≥ 1/(log d)c, or 2) ρ ≤ c1/log log d/log2 d and δ ≥ 1/dc. Here c is any constant and c1 is a small enough constant depending on c. The number of points that suffices is N = Õ(d) in the trigonometric setting for random x i or arbitrary x i that are roughly equally spaced, or in the algebraic setting when the x i are chosen according to the Chebyshev distribution, and N = Õ(d2) in the algebraic setting with random (or roughly equally spaced) x i.

STOC Conference 2015 Conference Paper

Rectangles Are Nonnegative Juntas

• Mika Göös
• Shachar Lovett
• Raghu Meka
• Thomas Watson 0001
• David Zuckerman

We develop a new method to prove communication lower bounds for composed functions of the form f o g n where f is any boolean function on n inputs and g is a sufficiently "hard" two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of f o g n can be simulated by a nonnegative combination of juntas. This is the strongest yet formalization for the intuition that each low-communication randomized protocol can only "query" few inputs of f as encoded by the gadget g. Consequently, we characterize the communication complexity of f o g n in all known one-sided zero-communication models by a corresponding query complexity measure of f. These models in turn capture important lower bound techniques such as corruption, smooth rectangle bound, relaxed partition bound, and extended discrepancy. As applications, we resolve several open problems from prior work: We show that SBPcc (a class characterized by corruption) is not closed under intersection. An immediate corollary is that MAcc ≠ SBPcc. These results answer questions of Klauck (CCC 2003) and Bohler et al. (JCSS 2006). We also show that approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. (ICALP) for partial matrices.

FOCS Conference 2014 Conference Paper

Non-malleable Codes against Constant Split-State Tampering

• Eshan Chattopadhyay
• David Zuckerman

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs [1] as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions F consists of a randomized encoding function Enc and a deterministic decoding function Dec such that for any m, Dec(Enc(m)) = m. Further, for any tampering function f ∈ F and any message m, Dec(f(Enc(m))) is either m or is ∈-close to a distribution D f independent of m, where ∈ is called the error. Of particular importance are non-malleable codes in the C-split-state model. In this model, the codeword is partitioned into C equal sized blocks and the tampering function family consists of functions (f 1, .. ., f C ) such that fi acts on the ith block. For C = 1 there cannot exist non-malleable codes. For C = 2, the best known explicit construction is by Aggarwal, Dodis and Lovett [2] who achieve rate = Ω(n -6/7 ) and error = 2 -Ω(n-1/7), where n is the block length of the code. In our main result, we construct efficient non-malleable codes in the C-split-state model for C = 10 that achieve constant rate and error = 2 -Ω(n). These are the first explicit codes of constant rate in the C-split-state model for any C = o(n), that do not rely on any unproven assumptions. We also improve the error in the explicit nonmalleable codes constructed in the bit tampering model by Cheraghchi and Guruswami [3]. Our constructions use an elegant connection found between seedless non-malleable extractors and non-malleable codes by Cheraghchi and Guruswami [3]. We explicitly construct such seedless non-malleable extractors for 10 independent sources and deduce our results on non-malleable codes based on this connection. Our constructions of extractors use encodings and a new variant of the sumproduct theorem.

FOCS Conference 2012 Conference Paper

Pseudorandomness from Shrinkage

• Russell Impagliazzo
• Raghu Meka
• David Zuckerman

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models where we don't know superpolynomial lower bounds but do know lower bounds of a fixed polynomial. We show that when such lower bounds are proved using random restrictions, we can construct PRGs which are essentially best possible without in turn improving the lower bounds. More specifically, say that a circuit family has shrinkage exponent Γ if a random restriction leaving a p fraction of variables unset shrinks the size of any circuit in the family by a factor of p Γ+o(1). Our PRG uses a seed of length s 1/(Γ+1)+o(1) to fool circuits in the family of size s. By using this generic construction, we get PRGs with polynomially small error for the following classes of circuits of size s and with the following seed lengths: 1) For de Morgan formulas, seed length s 1/3+o(1); 2) For formulas over an arbitrary basis, seed length s 1/2+o(1); 3) For read-once de Morgan formulas, seed length s. 234. .. ; 4) For branching programs of size s, seed length s 1/2+o(1). The previous best PRGs known for these classes used seeds of length bigger than n/2 to output n bits, and worked only when the size s = O(n) [1].

FOCS Conference 2011 Conference Paper

Privacy Amplification and Non-malleable Extractors via Character Sums

• Yevgeniy Dodis
• Xin Li 0006
• Trevor D. Wooley
• David Zuckerman

In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a non-malleable extractor. A non-malleable extractor dramatically strengthens the notion of a strong ex- tractor. A strong extractor takes two inputs, a weakly-random x and a uniformly random seed y, and outputs a string which appears uniform, even given y. For a non-malleable extractor nmExt, the output nmExt(x, y) should appear uniform given y as well as nmExt(x, A(y)), where A is an arbitrary function with A(y) ≠ y. We show that an extractor introduced by Chor and Goldreich is non-malleable when the entropy rate is above half. It outputs a linear number of bits when the entropy rate is 1/2 + α, for any α >; 0. Previously, no nontrivial parameters were known for any non-malleable extractor. To achieve a polynomial running time when outputting many bits, we rely on a widely-believed conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves a character sum estimate, which may be of independent interest. Using our non-malleable extractor, we obtain protocols for "privacy amplification": key agreement between two parties who share a weakly-random secret. Our protocols work in the presence of an active adversary with unlimited computational power, and have asymptotically optimal entropy loss. When the secret has entropy rate greater than 1/2, the protocol fol- lows from a result of Dodis and Wichs, and takes two rounds. When the secret has entropy rate δ for any constant δ >; 0, our new protocol takes a constant (polynomial in 1/δ) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.

STOC Conference 2011 Conference Paper

Pseudorandom generators for combinatorial shapes

• Parikshit Gopalan
• Raghu Meka
• Omer Reingold
• David Zuckerman

We construct pseudorandom generators for combinatorial shapes , which substantially generalize combinatorial rectangles, ε-biased spaces, 0/1 halfspaces, and 0/1 modular sums. A function f:[m] n -> {0,1} is an (m,n)-combinatorial shape if there exist sets A 1 ,...,A n ⊆ [m] and a symmetric function h:{0,1} n -> {0,1} such that f(x 1 ,...,x n ) = h(1 A 1 (x 1 ),...,1 A n (x n )). Our generator uses seed length O(log m + log n + log 2 (1/ε)) to get error ε. When m = 2, this gives the first generator of seed length O(log n) which fools all weight-based tests, meaning that the distribution of the weight of any subset is ε-close to the appropriate binomial distribution in statistical distance. For our proof we give a simple lemma which allows us to convert closeness in Kolmogorov (cdf) distance to closeness in statistical distance. As a corollary of our technique, we give an alternative proof of a powerful variant of the classical central limit theorem showing convergence in statistical distance, instead of the usual Kolmogorov distance.

FOCS Conference 2010 Conference Paper

Optimal Testing of Reed-Muller Codes

• Arnab Bhattacharyya 0001
• Swastik Kopparty
• Grant Schoenebeck
• Madhu Sudan 0001
• David Zuckerman

We consider the problem of testing if a given function f: F 2 n → F 2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al. [1] proposed and analyzed a natural 2 d+1 -query test for this problem. This test turned out to be intimately related to the Gowers norm. Alon et. al. showed that this test accepts every degree d polynomial with probability 1, while it rejects functions that are Ω(1)-far with probability Ω(1/(d2 d )). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Ω(2 -d )-far with Ω(1)probability (so the rejection probability is a universal constant independent of d and n). This implies a tight relationship between the (d + 1) st -Gowers norm of a function and its maximal correlation with degree d polynomials, when the correlation is close to 1. Our proof works by induction on n and yields a new analysis of even the classical Blum-Luby-Rubinfeld [2] linearity test, for the setting of functions mapping F 2 n to F 2. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [3], [4]. Our result has several implications. First, it shows that the Gowers norm test is tolerant, in that it also accepts close codewords. Second, it improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson [5]. Third, it implies a "query hierarchy" result for property testing of affine-invariant properties. That is, for every function q(n), it gives an affine-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of [6] for graph properties.

STOC Conference 2010 Conference Paper

Pseudorandom generators for polynomial threshold functions

• Raghu Meka
• David Zuckerman

We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed-length log n/ε O(d) fooling degree d PTFs with error at most ε. Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error ε. For the class of degree 1 threshold functions or halfspaces, we construct PRGs with much better dependence on the error parameter ε and obtain the following results. A PRG with seed length O(log n log(1/ε)) for error ε ≥ 1/poly(n). A PRG with seed length O(log n) for ε ≥ 1/poly(log n). Previously, only PRGs with seed length O(log n log 2 (1/ε)/ ε 2 ) were known for halfspaces. We also obtain PRGs with similar seed lengths for fooling halfspaces over the $n$ dimensional unit sphere.

STOC Conference 2008 Conference Paper

List-decoding reed-muller codes over small fields

• Parikshit Gopalan
• Adam R. Klivans
• David Zuckerman

We present the first local list-decoding algorithm for the r th order Reed-Muller code RM(2,m) over F for r ≥ 2. Given an oracle for a received word R: F m -< F, our randomized local list-decoding algorithm produces a list containing all degree r polynomials within relative distance (2 -r - ε) from R for any ε < 0 in time poly(m r ,ε -r ). The list size could be exponential in m at radius 2 -r , so our bound is optimal in the local setting. Since RM(2,m) has relative distance 2 -r , our algorithm beats the Johnson bound for r ≥ 2. In the setting where we are allowed running-time polynomial in the block-length, we show that list-decoding is possible up to even larger radii, beyond the minimum distance. We give a deterministic list-decoder that works at error rate below J(2 1-r ), where J(δ) denotes the Johnson radius for minimum distance δ. This shows that RM(2,m) codes are list-decodable up to radius η for any constant η < 1/2 in time polynomial in the block-length. Over small fields F q , we present list-decoding algorithms in both the global and local settings that work up to the list-decoding radius. We conjecture that the list-decoding radius approaches the minimum distance (like over F), and prove this holds true when the degree is divisible by q-1.

FOCS Conference 2008 Conference Paper

Network Extractor Protocols

• Yael Tauman Kalai
• Xin Li 0006
• Anup Rao 0001
• David Zuckerman

We design efficient protocols for processors to extract private randomness over a network with Byzantine faults, when each processor has access to an independent weakly-random n-bit source of sufficient min-entropy. We give several such network extractor protocols in both the information theoretic and computational settings. For a computationally unbounded adversary, we construct protocols in both the synchronous and asynchronous settings. These network extractors imply efficient protocols for leader election (synchronous setting only) and Byzantine agreement which tolerate a linear fraction of faults, even when the min-entropy is only 2 (log n) Omega(1). For larger min-entropy, in the synchronous setting the fraction of tolerable faults approaches the bounds in the perfect-randomness case. Our network extractors for a computationally bounded adversary work in the synchronous setting even when 99% of the parties are faulty, assuming trapdoor permutations exist. Further, assuming a strong variant of the Decisional Diffie-Hellman Assumption, we construct a network extractor in which all parties receive private randomness. This yields an efficient protocol for secure multi-party computation with imperfect randomness, when the number of parties is at least polylog (n) and where the parties only have access to an independent source with min-entropy n Omega(1).

STOC Conference 2006 Conference Paper

Deterministic extractors for small-space sources

• Jesse Kamp
• Anup Rao 0001
• Salil P. Vadhan
• David Zuckerman

We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on (0,1) n as sources generated by width 2 s branching programs: For every constant δ>0, we can extract .99 δ n bits that are exponentially close to uniform (in variation distance) from space s sources of min-entropy δ n, where s=Ω(n). In addition, assuming an efficient deterministic algorithm for finding large primes, there is a constant η > 0 such that for any δ>n -η , we can extract m=(δ-δ)n bits that are exponentially close to uniform from space s sources with min-entropy δ n, where s=Ω(β 3 n). Previously, nothing was known for δ ≤ 1/2, even for space 0.Our results are obtained by a reduction to a new class of sources that we call independent-symbol sources, which generalize both the well-studied models of independent sources and symbol-fixing sources. These sources consist of a string of n independent symbols over a d symbol alphabet with min-entropy k. We give deterministic extractors for such sources when k is as small as polylog(n), for small enough d.

STOC Conference 2006 Conference Paper

Linear degree extractors and the inapproximability of max clique and chromatic number

• David Zuckerman

FOCS Conference 2004 Conference Paper

Testing Low-Degree Polynomials over Prime Fields

• Charanjit S. Jutla
• Anindya C. Patthak
• Atri Rudra
• David Zuckerman

We present an efficient randomized algorithm to test if a given function f: F/sub p/ /sup n/ /spl rarr/ F/sub p/ (where p is a prime) is a low-degree polynomial. This gives a local test for generalized Reed-Muller codes over prime fields. For a given integer t and a given real /spl epsiv/ > 0, the algorithm queries f at 1//spl epsiv/ + t/spl middot/p/sup 2r/p-1+O(1)/ points to determine whether f can be described by a polynomial of degree at most t. If f is indeed a polynomial of degree at most t, our algorithm always accepts, and if f has a relative distance at least e from every degree t polynomial, then our algorithm rejects f with probability at least 1/2. Our result is almost optimal since any such algorithm must query f on at least /spl Omega/(1//spl epsiv/ + p/sup r+1/p-1/) points.

FOCS Conference 2003 Conference Paper

Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography

• Jesse Kamp
• David Zuckerman

We give an efficient deterministic algorithm which extracts /spl Omega/(n/sup 2/spl gamma//) almost-random bits from sources where n/sup 1/2 + /spl gamma// of the n bits are uniformly random and the rest are fixed in advance. This improves on previous constructions which required that at least n/2 of the bits be random. Our construction also gives explicit adaptive exposure-resilient functions and in turn adaptive all-or-nothing transforms. For sources where instead of bits the values are chosen from [d], for d > 2, we give an algorithm which extracts a constant fraction of the randomness. We also give bounds on extracting randomness for sources where the fixed bits can depend on the random bits.

STOC Conference 2001 Conference Paper

Extractor codes

• Amnon Ta-Shma
• David Zuckerman

We define new error correcting codes based on extractors. We show that for certain choices of parameters these codes have better list decoding properties than are known for other codes, and are provably better than Reed-Solomon codes. We further show that codes with strong list decoding properties are equivalent to slice extractors, a variant of extractors. We give an application of extractor codes to extracting many hardcore bits from a one-way function, using few auxiliary random bits. Finally, we show that explicit slice extractors for certain other parameters would yield optimal bipartite Ramsey graphs.

FOCS Conference 2001 Conference Paper

Extractors from Reed-Muller Codes

• Amnon Ta-Shma
• David Zuckerman
• Muli Safra

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/.

STOC Conference 2001 Conference Paper

Interaction in quantum communication and the complexity of set disjointness

• Hartmut Klauck
• Ashwin Nayak 0001
• Amnon Ta-Shma
• David Zuckerman

One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios there are ways of conveying information with exponentially fewer qubits than possible classically [3, 26]. Moreover, these methods have a very simple structure---they involve only few message exchanges between the communicating parties.

STOC Conference 2001 Conference Paper

Loss-less condensers, unbalanced expanders, and extractors

• Amnon Ta-Shma
• Chris Umans
• David Zuckerman

An extractor is a procedure which extracts randomness from a detective random source using a few additional random bits. Explicit extractor constructions have numerous applications and obtaining such constructions is an important derandomization goal. Trevisan recently introduced an elegant extractor construction, but the number of truly random bits required is suboptimal when the input source has low-min-entropy. Significant progress toward overcoming this bottleneck has been made, but so far has required complicated recursive techniques that lose the simplicity of Trevisan's construction. We give a clean method for overcoming this bottleneck by constructing {\em loss-less condensers}. which compress the n -bit input source without losing any min-entropy, using O(\log n) additional random bits. Our condensers are built using a simple modification of Trevisan's construction, and yield the best extractor constructions to date. Loss-less condensers also produce unbalanced bipartite expander graphs with small (polylogarithmic) degree D and very strong expansion of (1-\epilon)D . We give other applications of our construction, including dispersers with entropy loss O(\log n) , depth two super-concentrators whose size is within a polylog of optimal, and an improved hardness of approximation result.

STOC Conference 1999 Conference Paper

Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model

• Alexander Russell
• Michael E. Saks
• David Zuckerman

FOCS Conference 1998 Conference Paper

Perfect Information Leader Election in log* n + O (1) Rounds

• Alexander Russell
• David Zuckerman

In the leader election problem, n players wish to elect a random leader. The difficulty is that some coalition of players may conspire to elect one of its own members. We adopt the perfect information model: all communication is by broadcast, and the bad players have unlimited computational power. Within a round, they may also wait to see the inputs of the good players. A protocol is called resilient if a good leader is elected with probability bounded away from 0. We give a simple, constructive leader election protocol that is resilient against coalitions of size /spl beta/n, for any /spl beta/<1/2. Our protocol takes log*n+O(1) rounds, each player sending at most log n bits per round. For any constant k, our protocol can be modified to take k rounds and be resilient against coalitions of size /spl epsi/n(log/sup (k)/n)/sup 3/, where /spl epsi/ is a small enough constant and log(k) denotes the logarithm iterated k times. This is constructive for k/spl ges/3.

SODA Conference 1997 Conference Paper

Asymptotically Good Codes Correcting Insertions, Deletions, and Transpositions (Preliminary Version)

• Leonard J. Schulman
• David Zuckerman

STOC Conference 1996 Conference Paper

Randomness-Optimal Sampling, Extractors, and Constructive Leader Election

• David Zuckerman

STOC Conference 1995 Conference Paper

Tight analyses of two local load balancing algorithms

• Bhaskar Ghosh
• Frank Thomson Leighton
• Bruce M. Maggs
• S. Muthukrishnan 0001
• C. Greg Plaxton
• Rajmohan Rajaraman
• Andréa W. Richa
• Robert Endre Tarjan

FOCS Conference 1994 Conference Paper

Computing with Very Weak Random Sources

• Aravind Srinivasan
• David Zuckerman

For any fixed /spl epsiv/>0, we show how to simulate RP algorithms in time n/sup O(log n/) using the output of a /spl delta/-source with min-entropy R(/spl epsiv/). Such a weak random source is asked once for R(/spl epsiv/) bits; it outputs an R-bit string such that any string has probability at most 2/sup -R/(/spl epsiv//). If /spl epsiv/>1-1/(k+1), our BPP simulations take time n/sup O(log(k/ n)) (log/sup (k/) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy R/sup /spl Omega/(1/), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson. >

STOC Conference 1993 Conference Paper

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

• Nati Linial
• Michael Luby
• Michael E. Saks
• David Zuckerman

STOC Conference 1993 Conference Paper

Expanders that beat the eigenvalue bound: explicit construction and applications

• Avi Wigderson
• David Zuckerman

STOC Conference 1993 Conference Paper

Lower bounds for randomized mutual exclusion

• Eyal Kushilevitz
• Yishay Mansour
• Michael O. Rabin
• David Zuckerman

STOC Conference 1993 Conference Paper

More deterministic simulation in logspace

• Noam Nisan
• David Zuckerman

FOCS Conference 1991 Conference Paper

Simulating BPP Using a General Weak Random Source

• David Zuckerman

It is shown how to simulate BPP and approximation algorithms in polynomial time using the output from a delta -source. A delta -source is a weak random source that is asked only once for R bits, and must output an R-bit string according to some distribution that places probability no more than 2/sup - delta R/ on any particular string. Also given are two applications: one to show the difficulty of approximating the size of the maximum clique, and the other to the problem of implicit O(1) probe search. >

STOC Conference 1990 Conference Paper

A Technique for Lower Bounding the Cover Time

• David Zuckerman

FOCS Conference 1990 Conference Paper

General Weak Random Sources

• David Zuckerman

The following model for a weak random source is considered. The source is asked only once for R bits, and the source outputs an R-bit string such that no string has probability more than 2/sup - delta R/ of being output. for some fixed delta >0. A pseudorandom generator that runs in time n/sup O(log n)/ and simulates RP using as a seed a string from such a source is exhibited. Under the generalized Paley graph conjecture, a generator that runs in polynomial time and simulates RP is given, as well as a different generator that produces almost perfectly random bits at a rate arbitrarily close to optimal using as seeds strings from a constant number of independent weak random sources. >

FOCS Conference 1990 Conference Paper

Security Preserving Amplification of Hardness

• Oded Goldreich 0001
• Russell Impagliazzo
• Leonid A. Levin
• Ramarathnam Venkatesan
• David Zuckerman

The task of transforming a weak one-way function (which may be easily inverted on all but a polynomial fraction of the range) into a strong one-way function (which can be easily inverted only on a negligible function of the range) is considered. The previously known transformation does not preserve the security (i. e. the running time of the inverting algorithm) within any polynomial. Its resulting function, F(x), applies the weak one-way function to many small (of length mod x mod /sup theta /, theta >

FOCS Conference 1989 Conference Paper

How to Recycle Random Bits

• Russell Impagliazzo
• David Zuckerman

It is shown that modified versions of the linear congruential generator and the shift register generator are provably good for amplifying the correctness of a probabilistic algorithm. More precisely, if r random bits are needed for a BPP algorithm to be correct with probability at least 2/3, then O(r+k/sup 2/) bits are needed to improve this probability to 1-2/sup -k/. A different pseudorandom generator that is optimal, up to a constant factor, in this regard is also presented. It uses only O(r+k) bits to improve the probability to 1-2/sup -k/. This generator is based on random walks on expanders. The results do not depend on any unproven assumptions. It is shown that the modified versions of the shift register and linear congruential generators can be used to sample from distributions using, in the limit, the information-theoretic lower bound on random bits. >