When a Markov chain models nature or social interactions, it is likely not followed exactly, but only approximately. We therefore introduce several notions of robustness for a Markov chain P. Our standard adversary can dynamically change transition probabilities of P by 1 ± ε, and our strong adversary can completely control each transition independently with probability ε, as in a model by Azar, Broder, Karlin, Linial, and Philips [Y. Azar et al., 1996]. These adversaries are equivalent up to constant factors if the degrees are constant. Our adversarial chains need not converge. We define and prove various robustness properties of a reversible chain P, i.e., a random walk on a connected undirected graph G. Let d be the maximum degree, Δ the diameter, π the stationary distribution, and t_{mix} the mixing time. 1) We define a natural analogue π^+(S) that upper bounds limiting frequencies in a set S in the adversarial chain. We show that if ε = O(1/√{dt_{up}}), where t_{up} is a variant of the mixing time, then π^+(S) = O(π(S)^{1-α}) for any α > 0. 2) We define the mixing time robustness as the largest ε such that the approximate mixing time increases by only a constant factor, and prove that it is Ω(1/√{dt_{mix}}). 3) We define the hitting time robustness as the largest ε such that the maximum hitting time increases by only a constant factor, and show that it is Ω(1/t_{mix}). For trees, we show it is Ω(1/Δ). 4) We define the cover time robustness as the largest ε such that the cover time increases by only a constant factor. We show that in most graphs it’s at least the hitting time robustness. 5) We characterize the mixing, hitting, and cover time robustnesses for constant-degree regular expander graphs up to constant factors. They are Θ(1), Θ(1/log n), and Θ(1/log n), respectively.

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.

A Chor–Goldreich (CG) source is a sequence of random variables X = X1 ∘ … ∘ Xt, where each Xi ∼ {0,1}d and Xi has δ d min-entropy conditioned on any fixing of X1 ∘ … ∘ Xi−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 Xi to only have conditional Shannon entropy δ d.

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map f : Fqr → Fqn to an element sampled uniformly at random from a k-dimensional variety V ⊆ Fqr. 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).

Recently, there has been exciting progress in understanding the complexity of distributions. Here, the goal is to quantify the resources required to generate (or sample) a distribution. Proving lower bounds in this new setting is more challenging than in the classical setting, and has yielded interesting new techniques and surprising applications. In this work, we initiate a study of the complexity of sampling with limited memory, and obtain the first nontrivial sampling lower bounds against oblivious read-once branching programs (ROBPs). In our first main result, we show that any distribution sampled by an ROBP of width 2^{Ω(n)} has statistical distance 1-2^{-Ω(n)} from any distribution that is uniform over a good code. More generally, we obtain sampling lower bounds for any list decodable code, which are nearly tight. Previously, such a result was only known for sampling in AC⁰ (Lovett and Viola, CCC'11; Beck, Impagliazzo and Lovett, FOCS'12). As an application of our result, a known connection implies new data structure lower bounds for storing codewords. In our second main result, we prove a direct product theorem for sampling with ROBPs. Previously, no direct product theorems were known for the task of sampling, for any computational model. A key ingredient in our proof is a simple new lemma about amplifying statistical distance between sequences of somewhat-dependent random variables. Using this lemma, we also obtain a simple new proof of a known lower bound for sampling disjoint sets using two-party communication protocols (Göös and Watson, RANDOM'19).

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 NP ∩ coNP circuits, formally known as randomized SVN circuits, we convert any randomized algorithm over inputs of length n running in time t ≥ n into a deterministic one running in time t 2+α for an arbitrarily small constant α > 0. Such a slowdown is nearly optimal for t close to n , since under standard 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.

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

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 t2+α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.

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1. For any eps > 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1 - eps, but G's adjacency matrix has more than exp(log^delta n) eigenvalues larger than 1 - eps, where delta depends only on eps. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2. A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of K^polylog(K), improving over the previously known gadget with blowup of 2^K. 3. An n variable integrality gap for Unique Games that that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube.

A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over F2. We introduce a new technique to prove such correlation bounds with F2 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.

We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order and acceptance probability at least $\epsilon$. When $r = w$, our generator has seed length $O(\log^2 r + \log(1/\epsilon))$. When $r = \text{polylog } w$, our generator has optimal seed length $O(\log w + \log(1/\epsilon))$. 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 [ SIAM J. Comput., (2020), doi:10.1137/18M1197734]. In addition, our generator and its analysis are dramatically simpler than the work by Braverman et al. When $\epsilon$ is small, our generator's seed length improves on all the classic generators for space-bounded computation [N. Nisan, Combinatorica, 12 (1992), pp. 449--461; R. Impagliazzo, N. Nisan, and A. Wigderson, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, ACM, 1994, pp. 356--364; N. Nisan and D. Zuckerman, J. Comput. System Sci., 52 (1996), pp. 43--52]. However, all of these other works construct more general objects than we do. 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 $\epsilon$ can be simulated deterministically in space $O(\log^{3/2} n + \log n \log \log(1/\epsilon))$. This space bound improves on work by Saks and Zhou [ J. Comput. System Sci., 58 (1999), pp. 376--403], who gave an algorithm for the more general “two-sided” problem that runs in space $O(\log^{3/2} n + \sqrt{\log n} \log(1/\epsilon))$.

The seminal result of Kahn, Kalai and Linial shows that a coalition of O(n/(log n)) players can bias the outcome of any Boolean function {0,1}^n -> {0,1} with respect to the uniform measure. We extend their result to arbitrary product measures on {0,1}^n, by combining their argument with a completely different argument that handles very biased input bits. We view this result as a step towards proving a conjecture of Friedgut, which states that Boolean functions on the continuous cube [0,1]^n (or, equivalently, on {1,...,n}^n) can be biased using coalitions of o(n) players. This is the first step taken in this direction since Friedgut proposed the conjecture in 2004. Russell, Saks and Zuckerman extended the result of Kahn, Kalai and Linial to multi-round protocols, showing that when the number of rounds is o(log^* n), a coalition of o(n) players can bias the outcome with respect to the uniform measure. We extend this result as well to arbitrary product measures on {0,1}^n. The argument of Russell et al. relies on the fact that a coalition of o(n) players can boost the expectation of any Boolean function from epsilon to 1-epsilon with respect to the uniform measure. This fails for general product distributions, as the example of the AND function with respect to mu_{1-1/n} shows. Instead, we use a novel boosting argument alongside a generalization of our first result to arbitrary finite ranges.

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer from a quantitative loss in parameters, and hence do not give nontrivial implications for models where we don’t know super-polynomial 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 for size s = O ( n ) [8].

Arora et al. [S. Arora, B. Barak, M. Brunnermeier, and R. Ge, Comm. ACM, 54 (2011), pp. 101--107] showed that taking computational complexity into account, a dishonest seller could strategically place lemons in financial derivatives to make them substantially less valuable to buyers. We show that if the seller is required to construct derivatives of a certain form, then this phenomenon disappears. In particular, we define and construct pseudorandom derivative families, for which lemon placement only slightly affects the values of the derivatives. Our constructions use expander graphs. We study our derivatives in a more general setting than Arora et al. In particular, we analyze arbitrary tranches of the common collateralized debt obligations (CDOs) when the underlying assets can have significant dependencies.

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

We study how to extract randomness from a C-interleaved source, that is, a source comprised of C independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields: (1) For some delta>0, c>0, explicit extractors for 2-interleaved sources on {0,1}^{2n} when one source has min-entropy at least (1-delta)*n and the other has min-entropy at least c*log(n). The best previous construction, by Raz and Yehudayoff, worked only when both sources had entropy rate 1-delta. (2) For some c>0 and any large enough prime p, explicit extractors for 2-interleaved sources on [p]^{2n} when one source has min-entropy rate at least .51 and the other source has min-entropy rate at least (c*log(n))/n. We use these to obtain the following applications: (a) We introduce the class of any-order-small-space sources, generalizing the class of small-space sources studied by Kamp et al.. We construct extractors for such sources with min-entropy rate close to 1/2. Using the Raz-Yehudayoff construction would require entropy rate close to 1. (b) For any large enough prime p, we exhibit an explicit function f:[p]^{2n} -> {0,1} such that the randomized best-partition communication complexity of f with error 1/2-2^{-Omega(n)} is at least .24*n*log(p). Previously this was known only for a tiny constant instead of .24, for p=2 by by Raz and Yehudayoff. We introduce non-malleable extractors in the interleaved model. For any large enough prime p, we give an explicit construction of a weak-seeded non-malleable extractor for sources over [p]^n with min-entropy rate .51. Nothing was known previously, even for almost full min-entropy.

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 (xi, yi) ε [-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(xi) - yi|≤ δ. 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 xior arbitrary xithat are roughly equally spaced, or in the algebraic setting when the xiare chosen according to the Chebyshev distribution, and N = Õ(d2) in the algebraic setting with random (or roughly equally spaced) xi.

We explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least $\mathrm{log}^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$. M A key ingredient in our construction is an explicit construction of a monotone, almost-balanced Boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$ for any $\delta>0$. 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 $\mathrm{polylog}(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola, achieved $q=n^{1/2-\delta}$. Our explicit two-source extractor directly implies an explicit construction of a $2^{(\mathrm{log}\ \mathrm{log}\ N)^{O(1)}}$-Ramsey graph over $N$ vertices, improving bounds obtained by Barak et al. and matching an independent work by Cohen.

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ 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 \circ g^n$ can be simulated by a nonnegative combination of juntas. This is a new formalization for the intuition that each low-communication randomized protocol can only “query” a few inputs of $f$ as encoded by the gadget $g$. Consequently, we characterize the communication complexity of $f\circ g^n$ in all known one-sided (i.e., not closed under complement) 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 $\mathsf{SBP}^{\sf cc}$ (a class characterized by corruption) is not closed under intersection. An immediate corollary is that $\mathsf{MA}^{\sf cc} \neq \mathsf{SBP}^{\sf cc}$. These results answer questions of Klauck [Proceedings of the 18th Conference on Computational Complexity (CCC), IEEE Computer Society, Los Alamitos, CA, 2003, pp. 118--134] and Böhler, Glasser, and Meister [J. Comput. System Sci., 72 (2006), pp. 1043--1076]. We also show that the approximate nonnegative rank of partial boolean matrices does not admit efficient error reduction. This answers a question of Kol et al. [Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Springer, Berlin, 2014, pp. 701--712] for partial matrices. In subsequent work, our structure theorem has been applied to resolve the communication complexity of the clique versus independent set problem.

We propose a new model of a weakly random source that admits randomness extraction. Our model of additive sources includes such natural sources as uniform distributions on arithmetic progressions (APs), generalized arithmetic progressions (GAPs), and Bohr sets, each of which generalizes affine sources. We give an explicit extractor for additive sources with linear min-entropy over both Zp and Zn/p, for large prime p, although our results over Zn/p require that the source further satisfy a list-decodability condition. As a corollary, we obtain explicit extractors for APs, GAPs, and Bohr sources with linear min-entropy, although again our results over Zn/p require the list-decodability condition.

We develop a new method to prove communication lower bounds for composed functions of the form f o gn 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 gn 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 gn 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.

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for “easy” Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an n-variate Boolean function f computable by some unknown small circuit from a known class of circuits, find in deterministic time poly(2n) a circuit C (no restriction on the type of C) computing f so that the size of C is less than the trivial circuit size 2n/n. We get nontrivial compression for functions computable by AC0circuits, (de Morgan) formulas, and (read-once) branching programs of the size for which the lower bounds for the corresponding circuit class are known. These compression algorithms rely on the structural characterizations of “easy” functions, which are useful both for proving circuit lower bounds and for designing “meta-algorithms” (such as Circuit-SAT). For (de Morgan) formulas, such structural characterization is provided by the “shrinkage under random restrictions” results [52], [21], strengthened to the “high-probability” version by [48], [26], [33]. We give a new, simple proof of the “high-probability” version of the shrinkage result for (de Morgan) formulas, with improved parameters. We use this shrinkage result to get both compression and #SAT algorithms for (de Morgan) formulas of size about n2. We also use this shrinkage result to get an alternative proof of the recent result by Komargodski and Raz [33] of the average-case lower bound against small (de Morgan) formulas. Finally, we show that the existence of any non-trivial compression algorithm for a circuit class C ⊆ P/poly would imply the circuit lower bound NEXP ⊈ C. This complements Williams's result [55] that any non-trivial Circuit-SAT algorithm for a circuit class C would imply a superpolynomial lower bound against C for a language in NEXP1.

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 Dfindependent 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 (f1, . . . , fC) 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.

In studying how to communicate over a public channel with an active adversary, Dodis and Wichs introduced the notion of a nonmalleable extractor. A nonmalleable extractor dramatically strengthens the notion of a strong extractor. 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 nonmalleable extractor ${\mathsf{nmExt}}$, the output ${\mathsf{nmExt}}(x,y)$ should appear uniform given $y$ as well as ${\mathsf{nmExt}}(x,{\mathcal A}(y))$, where ${\mathcal A}$ is an arbitrary function with ${\mathcal A}(y) \neq y$. We show that an extractor introduced by Chor and Goldreich is nonmalleable when the entropy rate (the ratio between the entropy and the length of the weakly random string) is above half. It outputs a linear number of bits when the entropy rate is $1/2 + \alpha$ for any $\alpha>0$. Previously, no explicit construction was known for any entropy rate less than 1. To achieve a polynomial running time when outputting more than one bit, we rely on a widely believed conjecture about the distribution of prime numbers in arithmetic progressions. Our analysis involves character sum estimates, which may be of independent interest. Using our nonmalleable 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 follows from a result of Dodis and Wichs and takes two (or three, for strongest security guarantees) rounds. When the secret has entropy rate $\delta$ for any constant $\delta>0$, our new protocol takes a constant (polynomial in $1/\delta$) number of rounds. Our protocols run in polynomial time under the above well-known conjecture about primes.

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, $\epsilon$-biased spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n\rightarrow\{0,1\}$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n\subseteq[m]$ and a symmetric function $h:\{0,1\}^n\rightarrow\{0,1\}$ such that $f(x_1,\ldots,x_n)=h(1_{A_1}(x_1),\ldots,1_{A_n}(x_n))$. Our generator uses seed-length $O(\log m+\log n+\log^2(1/\varepsilon))$ to get error $\varepsilon$. When $m=2$, this gives the first generator of seed-length $O(\log n)$ that fools all weight-based tests, meaning that the distribution of the weight of any subset is $\varepsilon$-close to the appropriate binomial distribution in statistical distance. Along the way, we give a generator for combinatorial rectangles with seed-length $O(\log^{3/2}n)$ and error $1/\mathrm{poly}(n)$, matching Lu's bound from ICALP 1998. 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.

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/\epsilon^{O(d)}$ fooling degree $d$ PTFs with error at most $\epsilon$. Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error $\epsilon$. For the class of degree $1$ threshold functions or halfspaces, previously only PRGs with seed length $O(\log n \log^2(1/\epsilon)/\epsilon^2)$ were known. We improve this dependence on the error parameter and construct PRGs with seed length $O(\log n + \log^2 (1/\epsilon))$ that $\epsilon$-fool halfspaces. We also obtain PRGs with similar seed lengths for fooling halfspaces over the $n$-dimensional unit sphere. The main theme of our constructions and analysis is the use of invariance principles to construct PRGs. We also introduce the notion of monotone read-once branching programs, which is key to improving the dependence on the error rate $\epsilon$ for halfspaces. These techniques may be of independent interest.

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 s1/(Γ+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 s1/3+o(1); 2) For formulas over an arbitrary basis, seed length s1/2+o(1); 3) For read-once de Morgan formulas, seed length s.234...; 4) For branching programs of size s, seed length s1/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].

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.

Arora, Barak, Brunnermeier, and Ge showed that taking computational complexity into account, a dishonest seller could dramatically increase the lemon costs of a family of financial derivatives. We show that if the seller is required to construct derivatives of a certain form, then this phenomenon disappears. In particular, we define and construct pseudorandom derivative families, for which lemon placement only slightly affects the values of the derivatives. Our constructions use expander graphs.We study our derivatives in a more general setting than Arora et al. In particular, we analyze arbitrary tranches of the common collateralized debt obligations (CDOs) when the underlying assets can have significant dependencies.

... under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes any product of discrete distributions with probabilities bounded away from 0. Our first main result shows that a recent pseudorandom generator construction of Meka and Zuckerman [MZ09], when suitably modified, can fool arbitrary functions of d halfspaces under product distributions where each coordinate has bounded fourth moment. To ǫ-fool any size-s, depth-d decision tree of halfspaces, our pseudorandom generator uses seed length O((dlog(ds/ǫ)+logn)·log(ds/ǫ)). For monotone functions of d halfspaces, the seed length can be improved to O((dlog(d/ǫ)+logn)·log(d/ǫ)). We get better bounds for larger ǫ; for example, to1/polylog(n)-foolallmonotonefunctionsof(logn)/loglognhalfspaces,ourgeneratorrequires a seed of length just O(logn). Our second main result generalizes the work of Diakonikolas et al. [DGJ + 09] to show that bounded independence suffices to fool functions of halfspaces under product distributions. Assuming each coordinatesatisfiesacertainstrongermoment condition, we showthat anyfunction computable by a size-s, depth-d decision tree of halfspaces is ǫ-fooled by Õ(d4 s 2 /ǫ 2)-wise independence. Our technical contributions include: a new multidimensional version of the classical Berry-Esseen theorem; a derandomization thereof; a generalization of Servedio [Ser07]’s regularity lemma for halfspaceswhichworksunderanyproduct distribution with bounded fourth moments; an extension of this regularity lemma to functions of many halfspaces; and, new analysis of the sandwiching polynomials technique of Bazzi [Baz09] for arbitrary product distributions.

We consider the problem of testing if a given function f:F2n→ F2is 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 2d+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/(d2d)). 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 F2nto F2. 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.

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 log2(1/ε)/ ε2) were known for halfspaces. We also obtain PRGs with similar seed lengths for fooling halfspaces over the $n$ dimensional unit sphere.

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(logn)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 nOmega(1).

We present the first local list-decoding algorithm for the rth order Reed-Muller code RM(2,m) over F for r ≥ 2. Given an oracle for a received word R: Fm -< 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(mr,ε-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(21-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 Fq, 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.

We give an efficient deterministic algorithm that extracts $\Omega(n^{2\gamma})$ almost‐random bits from sources where $n^{\frac{1}{2}+\gamma}$ of the n bits are uniformly random and the rest are fixed in advance. This improves upon previous constructions, which required that at least $n/2$ of the bits be random in order to extract many bits. Our construction also has applications in exposure‐resilient cryptography, giving 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 that 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.

In some scenarios there are ways of conveying information with many fewer, even exponentially fewer, qubits than possible classically. Moreover, some of these methods have a very simple structure-they involve only few message exchanges between the communicating parties. It is therefore natural to ask whether every classical protocol may be transformed to a "simpler" quantum protocol-one that has similar efficiency, but uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity. This, in particular, proves a round hierarchy theorem for quantum communication complexity, and implies, via a simple reduction, an Omega(N1k/) lower bound for k message quantum protocols for Set Disjointness for constant k. Enroute, we prove information-theoretic lemmas, and define a related measure of correlation, the informational distance, that we believe may be of significance in other contexts as well

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 2s 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.

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, which use an arbitrarily small constant times log n additional random bits for sources with constant entropy rate. Our extractors and dispersers output 1-α fraction of the randomness, for any α>0.We use our dispersers to derandomize results of Hastad [23] and Feige-Kilian [19] and show that for all ε>0, approximating MAX CLIQUE and CHROMATIC NUMBER to within n1-ε are NP-hard. We also derandomize the results of Khot [29] and show that for some γ > 0, no quasi-polynomial time algorithm approximates MAX CLIQUE or CHROMATIC NUMBER to within n/2(log n)1-γ, unless NP = P.Our constructions rely on recent results in additive number theory and extractors by Bourgain-Katz-Tao [11], Barak-Impagliazzo-Wigderson [5], Barak-Kindler-Shaltiel-Sudakov-Wigderson [6], and Raz [36]. We also simplify and slightly strengthen key theorems in the second and third of these papers, and strengthen a related theorem by Bourgain [10].

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0, 1} n ). 1. We show how to compress sources X samplable by logspace machines to expected length H(X) + O(1). Our next results concern flat sources whose support is in P. 2. If H(X) ≤ k = n − O(log n), we show how to compress to expected length k + polylog(n − k). 3. If the support of X is the witness set for a self-reducible NP relation, then we show how to compress to expected length H(X) + 5.

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0, l}/sup n/). 1) We show how to compress sources X samplable by logspace machines to expected length H(X) + O(1). Our next results concern flat sources whose support is in P. 2) If H(X) /spl les/ k = n - O(log n), we show how to compress to length k + /spl delta//spl middot/ (n - k) for any constant /spl delta/ > 0; in quasi-polynomial time we show how to compress to length k + O(polylog log (n - k)) even if k = n -polylog(n). 3) If the support of X is the witness set for a self-reducible NP relation, then we show how to compress to expected length H(X) + 4.

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.

We study error-correcting codes for highly noisy channels. For example, every received signal in the channel may originate from some half of the symbols in the alphabet. Our main conceptual contribution is an equivalence between error-correcting codes for such channels and extractors. Our main technical contribution is a new explicit error-correcting code based on Trevisan's extractor that can handle such channels, and even noisier ones. Our new code has polynomial-time encoding and polynomial-time soft-decision decoding. We note that Reed-Solomon codes cannot handle such channels, and our study exposes some limitations on list decoding of Reed-Solomon codes. Another advantage of our equivalence is that when the Johnson bound is restated in terms of extractors, it becomes the well-known Leftover Hash Lemma. This yields a new proof of the Johnson bound which applies to large alphabets and soft decoding. Our explicit codes are useful in several applications. First, they yield algorithms to extract many hardcore bits using few auxiliary random bits. Second, they are the key tool in a recent scheme to compactly store a set of elements in a way that membership in the set can be determined by looking at only one bit of the representation. Finally, they are the basis for the recent construction of high-noise, almost-optimal rate list-decodable codes over large alphabets.

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.

We use expander graphs to provide efficient new constructions for two security applications: authentication of long digital streams over lossy networks and building scalable, robust overlay networks. Here is a summary of our contributions: (1) To authenticate long digital streams over lossy networks, we provide a construction with a provable lower bound on the ability to authenticate a packet - and that lower bound is independent of the size of the graph. To achieve this, we present an authentication expander graph with constant degree. (Previous work used authentication graphs but required graphs with degree linear in the number of vertices.) (2) To build efficient, robust, and scalable overlay networks, we provide a construction using undirected expander graphs with a provable lower bound on the ability of a broadcast message to successfully reach any receiver. This also gives us a new, more efficient solution to the decentralized certificate revocation problem.

Collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. We consider the perfect information model: all communication is by broadcast and corrupt players are computationally unbounded. Protocols in this model may involve many asynchronous rounds. We assume that honest players communicate only uniformly random bits. We demonstrate that any n-player coin-flipping protocol that is resilient against corrupt coalitions of linear size must use either at least [1/2 - o(1)]log * n communication rounds or at least [log (2k-1) n ] 1-o(1) communication bits in the kth round, where log (j) denotes the logarithm iterated j times. In particular, protocols using one bit per round require [1/2 - o(1)]log * n rounds. These bounds also apply to the leader election problem. The primary component of this result is a new bound on the influence of random sets of variables on Boolean functions. Finally, in the one-round case, using other methods we prove a new bound on the influence of sets of variables of size $\beta n$ for $\beta > 1/3$.

Informally, an error-correcting code has "nice" list-decodability properties if every Hamming ball of "large" radius has a "small" number of codewords in it. We report linear codes with nontrivial list-decodability: i.e., codes of large rate that are nicely list-decodable, and codes of large distance that are not nicely list-decodable. Specifically, on the positive side, we show that there exist codes of rate R and block length n that have at most c codewords in every Hamming ball of radius H/sup -1/(1-R-1/c)/spl middot/n. This answers the main open question from the work of Elias (1957). This result also has consequences for the construction of concatenated codes of good rate that are list decodable from a large fraction of errors, improving previous results of Guruswami and Sudan (see IEEE Trans. Inform. Theory, vol.45, p.1757-67, Sept. 1999, and Proc. 32nd ACM Symp. Theory of Computing (STOC), Portland, OR, p. 181-190, May 2000) in this vein. Specifically, for every /spl epsi/ > 0, we present a polynomial time constructible asymptotically good family of binary codes of rate /spl Omega/(/spl epsi//sup 4/) that can be list-decoded in polynomial time from up to a fraction (1/2-/spl epsi/) of errors, using lists of size O(/spl epsi//sup -2/). On the negative side, we show that for every /spl delta/ and c, there exists /spl tau/0, and an infinite family of linear codes {C/sub i/}/sub i/ such that if n/sub i/ denotes the block length of C/sub i/, then C/sub i/ has minimum distance at least /spl delta/ /spl middot/ n/sub i/ and contains more than c/sub 1/ /spl middot/ n/sub i//sup c/ codewords in some Hamming ball of radius /spl tau/ /spl middot/ n/sub i/. While this result is still far from known bounds on the list-decodability of linear codes, it is the first to bound the "radius for list-decodability by a polynomial-sized list" away from the minimum distance of the code.

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

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.

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

Collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. We consider the perfect information model: all communication is by broadcast and corrupt players are computationally unbounded. Protocols in this model may involve many asynchronous rounds; we focus on protocols which permit each player to broadcast a single bit per round. We demonstrate that any n-player coin-flipping protocol resilient against corrupt coalitions of linear size must use \\Theta 1=2 \\Gamma o(1) log n rounds of communication. Such a bound also applies to the leader election problem. This extends work of Kahn, Kalai, and Linial, who proved a similar result for single-round protocols. The primary component of the above result is a new bound on the influence of random sets of variables on Boolean functions. Finally, in the one-round case, we prove a new bound on the influence of sets of variables of size fin, for fi ? 1=3. e-ma...

This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within $O(\Delta / \alpha)$ steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most $O((d^2 \log n)/\alpha)$, where $\Delta$ is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and $\alpha$ is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion $\alpha$, and for any value $\Delta$, there exists an initial distribution of tokens with imbalance $\Delta$ for which the time to reduce the imbalance to even $\Delta/2$ is at least $\Omega(\Delta/\alpha)$. The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains $\Omega((d^2 \log n) / \alpha)$. Furthermore, we show that upon reaching a state with a global imbalance of $O((d^2 \log n)/\alpha)$, the time for this algorithm to locally balance the network can be as large as $\Omega(n^{1/2})$. We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step.

We give an efficient algorithm to extract randomness from a very weak random source using a small additional number t of truly random bits. Our work extends that of Nisan and Zuckerman [ J. Comput. System Sci., 52 (1996), pp. 43--52] in that t remains small even if the entropy rate is well below constant. A key application of this is in running randomized algorithms using such a very weak source of randomness. For any fixed $\gamma > 0$, we show how to simulate RP algorithms in time $n^{O(\log n)}$ using the output of a \ds\ with min-entropy $R^\gamma$. Such a weak random source is asked once for R bits; it outputs an R-bit string according to any probability distribution that places probability at most $2^{-R^\gamma}$ on each string. If $\gamma > 1/2$, our simulation also works for BPP; for $\gamma > 1-1/(k+1)$, our simulation takes time $n^{O(\logk n)}$ (log (k) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor--Goldreich sources of min-entropy $R^{\Omega(1)}$, which is optimal. We present applications to time-space tradeoffs, expander constructions, and to the hardness of approximation. Of independent interest is our randomness-efficient Leftover Hash Lemma, a key tool for extracting randomness from weak random sources.

We present simple, polynomial time encodable and decodable codes which are asymptotically good for channels allowing insertions, deletions, and transpositions. As a corollary, they achieve exponential error probability in a stochastic model of insertion-deletion.

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.

We establish, for the first time, lower bounds for randomized mutual exclusion algorithms (with a read-modify-write operation). Our main result is that a constant-size shared variable cannot guarantee strong fairness, even if randomization is allowed. In fact, we prove a lower bound of $\Omega (\log\log n)$ bits on the size of the shared variable, which is also tight. We investigate weaker fairness conditions and derive tight (upper and lower) bounds for them as well. Surprisingly, it turns out that slightly weakening the fairness condition results in an exponential reduction in the size of the required shared variable. Our lower bounds rely on an analysis of Markov chains that may be of interest on its own and may have applications elsewhere.

Article Free Access Share on Randomness-optimal sampling, extractors, and constructive leader election Author: David Zuckerman Dept. of Computer Sciences, The University of Texas at Austin, Austin, TX Dept. of Computer Sciences, The University of Texas at Austin, Austin, TXView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 286–295https://doi.org/10.1145/237814.237878Published:01 July 1996Publication History 24citation414DownloadsMetricsTotal Citations24Total Downloads414Last 12 Months20Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We prove that all of Karp’s 21 original $NP$-complete problems have a version that is hard to approximate. These versions are obtained from the original problems by adding essentially the same simple constraint. We further show that these problems are absurdly hard to approximate. In fact, no polynomial-time algorithm can even approximate $\log ^{(k)} $ of the magnitude of these problems to within any constant factor, where $\log ^{(k)} $ denotes the logarithm iterated k times, unless $NP$ is recognized by slightly superpolynomial randomized machines. We use the same technique to improve the constant $\epsilon $ such that MAX CLIQUE is hard to approximate to within a factor of $n^\epsilon $. Finally, we show that it is even harder to approximate two counting problems: counting the number of satisfying assignments to a monotone 2SAT formula and computing the permanent of $ - 1,0,1$ matrices.

. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d + 1 fewer tokens, where d is the maximum degree of any node in the network. We show that within O(\\Delta=ff) steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most O((d 2 log n)=ff), where \\Delta is the maximum difference between the number tokens at any node initially and the average number of tokens, n is the number of nodes in the network, and ff is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion ff, and for any value \\Delta, there exists an initial distribution of tokens with imbalance \\Delta for which the time to reduce the imbalance to even \\Delta=2 is at least \\Omega\\Gammaa =ff). The bound on the final imbalance is tight in the sense that there exists a cl...

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

We establish, for the first time, lower bounds for randomized mutual-exclusion algorithms (with a read-modify-write operation). Our main result is that a constant size shared-variable cannot guarantee strong fairness, even if randomization is allowed. In fact, we prove a lower bound of\\Omega\\Gamma/46 log n) bits on the size of the shared-variable, which is also tight. We investigate weaker fairness conditions and derive tight (upper and lower) bounds for them as well. Surprisingly, it turns out that slightly weakening the fairness condition results in an exponential reduction in the size of the required shared-variable. Our lower bounds rely on an analysis of Markovchains, that may be of interest on its own and may have applications elsewhere. Keywords: Mutual Exclusion, Randomized Distributed Algorithms, Markov-Chains, Lower-Bounds. 1 Introduction Randomization has played an important role in the design and understanding of distributed algorithms. It is a natural tool which is usual...

Given d, m and c, we deterministically produce a sequence of points S that hits every combinatorial rectangle in [m]d of volume at least 6.Both the running time of the algorithm and ISI are polynomial in m log(d) /c.This algorithm has applications to deterministic constructions of small sample spaces for general multivalued random variables.

We show that any randomized space(S) algorithm which uses only poly(S) random bits can be simulated deterministically in space(S), for S(n) ~log n.Of independent interest is our main technical tool: a procedure which extracts randomness from a defective random source using a small additional number of truly random bits.

For every n and 0 > b > 1, we construct graphs on n nodes such that every two sets of size n^b share an edge, having essentially optimal maximum degree n^{1-b+o(1)}. We use them to explicitly construct a k round sorting algorithm using n^{1+1/k+o(1)} comparisons; a k round selection algorithm using n^{1+1/(2^k-1)+o(1)} comparisons; a depth 2 superconcentrator of size n^{1+o(1)}; and a depth k wide-sense nonblocking generalized connector of size n^{1+1/k+o(1)}. All of these results improve on previous constructions by factors of n^{Omega(1)}, and are optimal to within factors of n^{o(1)}. These results are based on an improvement to the extractor construction of Nisan & Zuckerman: our algorithm extracts asymptotically the optimal number of random bits from a defective random source using a small additional number of truly random bits.

A general technique for proving lower bounds on expected covering times of random walks on graphs in terms of expected hitting times between vertices is given. This technique is used to prove (i) A tight bound of $\Omega ( | V |\log^2 | V | )$ for the two-dimensional torus; (ii) A tight bound of $\Omega ( | V |\log ^2 | V |/ \log d_{\max } )$ for trees with maximum degree $d_{\max } $; (iii) Tight bounds of $\Omega ( \mu ^ + \log ^2 | V | )$ for rapidly mixing walks on vertex transitive graphs, where $\mu^+$ denotes the maximum expected hitting time between vertices. In addition to these new results, the technique allows several known lower bounds on cover times to be systematically proved, often in a much simpler way. Finally, a different technique is used to prove an $\Omega ( 1 / ( 1 - \lambda _2 ) )$ lower bound on the cover time, where $\lambda_2 $ is the second largest eigenvalue of the transition matrix. This was previously known only in the case where the walk starts in the stationary distribution [J. Theoret. Probab., 2 (1989), pp. 101–120].

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

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>

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

We give a general technique for proving lower bounds on expected covering times of random walks on graphs in terms of expected hitting times between vertices.We use this teclmique to prove: i) A tight bound of ft(IVIlog~lll) for the 2dimensional torus.ii) A tight bound of ft(IV[log21VI/logdma,) for trees with maximum degree dma~.iii) Tight bounds of f2(p + log ]VI) for rapidly mixing walks on vertex transitive graphs, where p+ denotes the mmxinmm expected hitting time between vertices.In addition to these new results, our technique allows us to systema~icMly prove several known lower bounds on cover times, often in a much simpler way.Finally, we use a different technique to prove an .(2(1/(1-~2)) lower bound on the cover time.where A2 is the second largest eigenvalue of the transMon matrix.This was previously known only in the case where the walk starts in the stationary distribution [ iq.

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