We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows: 1) We consider read-once group-products over a finite group G, i.e., tests of the form ∏_{i=1}^n (g_i)^{x_i} where g_i ∈ G, a special case of read-once permutation branching programs. We give generators with optimal seed length c_G log(n/ε) over any p-group. The proof uses the small-bias plus noise paradigm, but derandomizes the noise to avoid the recursion in previous work. Our generator works when the bits are read in any order. Previously for any non-commutative group the best seed length was ≥ log n log(1/ε), even for a fixed order. 2) We give a reduction that "lifts" suitable generators for group products over G to a generator that fools width-w block products, i.e., tests of the form ∏ (g_i)^{f_i} where the f_i are arbitrary functions on disjoint blocks of w bits. Block products generalize several previously studied classes. The reduction applies to groups that are mixing in a representation-theoretic sense that we identify. 3) Combining (2) with (1) and other works we obtain new generators for block products over the quaternions or over any commutative group, with nearly optimal seed length. In particular, we obtain generators for read-once polynomials modulo any fixed m with nearly optimal seed length. Previously this was known only for m = 2. 4) We give a new generator for products over "mixing groups." The construction departs from previous work and uses representation theory. For constant error, we obtain optimal seed length, improving on previous work (which applied to any group). This paper identifies a challenge in the area that is reminiscent of a roadblock in circuit complexity - handling composite moduli - and points to several classes of groups to be attacked next.

We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tests better than bounded uniformity. We prove this for threshold tests, small-space algorithms, and small-depth circuits. In particular, we obtain small-bias distributions that - achieve an optimal lower bound on their statistical distance to any bounded-uniform distribution. This closes a line of research initiated by Alon, Goldreich, and Mansour in 2003, and improves on a result by O'Donnell and Zhao. - have heavier tail mass than the uniform distribution. This answers a question posed by several researchers including Bun and Steinke. - rule out a popular paradigm for constructing pseudorandom generators, originating in a 1989 work by Ajtai and Wigderson. This again answers a question raised by several researchers. For branching programs, our result matches a bound by Forbes and Kelley. Our small-bias distributions above are symmetric. We show that the xor of any two symmetric small-bias distributions fools any bounded function. Hence our examples cannot be extended to the xor of two small-bias distributions, another popular paradigm whose power remains unknown. We also generalize and simplify the proof of a result of Bazzi.

We study the communication complexity of multiplying$k\times t$elements from the group$H$= SL$(2, q)$in the number-on-forehead model with$k$parties. We prove a lower bound of$(t\log H)/c^{k}$. This is an exponential improvement over previous work, and matches the state-of-the-art in the area. Relatedly, we show that the convolution of$k^{c}$independent copies of a 3-uniform distribution over$H^{m}$is close to a$k$- uniform distribution. This is again an exponential improvement over previous work which needed$c^{k}$copies. The proofs are remarkably simple; the results extend to other quasirandom groups. We also show that for any group$LI$, any distribution over$H^{m}$whose weight-k Fourier coefficients are small is close to a k-uniform distribution. This generalizes previous work in the abelian setting, and the proof is simpler.

An n-bit boolean function is resilient to coalitions of size q if no fixed set of q bits is likely to influence the value of the function when the other n — q bits are chosen uniformly at random, even though the function is nearly balanced. We construct explicit functions resilient to coalitions of size q = n/(log n)O(log log n) = n1-o(1) computable by linear-size circuits and linear-time algorithms. We also obtain a tight size-depth tradeoff for computing such resilient functions. Constructions such as ours were not available even non-explicitly. It was known that functions resilient to coalitions of size q = n0.63… can be computed by linear-size circuits [BL85], and functions resilient to coalitions of size q = Θ(n/ log2 n) can be computed by quadratic-size circuits [AL93]. One component of our proofs is a new composition theorem for resilient functions. * This paper subsumes an unpublished work by Meka. PI and EV are partially supported by NSF grant CCF-2114116.

We study a simple and general template for constructing affine extractors by composing a linear transformation with resilient functions. Using this we show that good affine extractors can be computed by non-explicit circuits of various types, including AC0-Xor circuits: AC0 circuits with a layer of parity gates at the input. We also show that one-sided extractors can be computed by small DNF-Xor circuits, and separate these circuits from other well-studied classes. As a further motivation for studying DNF-Xor circuits we show that if they can approximate inner product then small AC0-Xor circuits can compute it exactly - a long-standing open problem.

We revisit the problem of constructing explicit pseudorandom generators that fool with error ϵ degree-d polynomials in n variables over the field Fq, in the case of large q. Previous constructions either have seed length $\geq 2^{d}\log q$, and thus are only non-trivial when $d\lt \log n$, or else rely on a seminal reduction by Bogdanov (STOC 2005). This reduction yields seed length not less than $d^{4}\log n+\log q$ and requires fields of size $q\geq d^{6}/\epsilon^{2}$; and explicit generators meeting such bounds are known.Departing from Bogdanov’s reduction, we develop an algebraic analogue of the Bogdanov-Viola paradigm (FOCS 2007, SICOMP 2010) of summing generators for degree-one polynomials. Whereas previous analyses of the paradigm are restricted to degree $d\lt \log n$, we give a new analysis which handles large degrees. A main new idea is to show that the construction preserves indecomposability of polynomials. Apparently for the first time in the area, the proof uses invariant theory.Our approach in particular yields several new pseudorandom generators. In particular, for large enough fields we obtain seed length $O(d\log n+\log q)$ which is optimal up to constant factors. We also construct generators for fields of size as small as $O(d^{4})$. Further reducing the field size requires a significant change in techniques: Most or all generators for large-degree polynomials rely on Weil bounds; but such bounds are only applicable when $q\gt d^{4}$

International audience

The hardness vs. randomness paradigm aims to explicitly construct pseudorandom generators G:{0,1}^r → {0,1}^m that fool circuits of size m, assuming the existence of explicit hard functions. A "high-end PRG" with seed length r = O(log m) (implying BPP=P) was achieved in a seminal work of Impagliazzo and Wigderson (STOC 1997), assuming the high-end hardness assumption: there exist constants 0 < β < 1 < B, and functions computable in time 2^{B ⋅ n} that cannot be computed by circuits of size 2^{β ⋅ n}. Recently, motivated by fast derandomization of randomized algorithms, Doron et al. (FOCS 2020) and Chen and Tell (STOC 2021), construct "extreme high-end PRGs" with seed length r = (1+o(1))⋅ log m, under qualitatively stronger assumptions. We study whether extreme high-end PRGs can be constructed from the corresponding hardness assumption in which β = 1-o(1) and B = 1+o(1), which we call the extreme high-end hardness assumption. We give a partial negative answer: - The construction of Doron et al. composes a PEG (pseudo-entropy generator) with an extractor. The PEG is constructed starting from a function that is hard for MA-type circuits. We show that black-box PEG constructions from the extreme high-end hardness assumption must have large seed length (and so cannot be used to obtain extreme high-end PRGs by applying an extractor). To prove this, we establish a new property of (general) black-box PRG constructions from hard functions: it is possible to fix many output bits of the construction while fixing few bits of the hard function. This property distinguishes PRG constructions from typical extractor constructions, and this may explain why it is difficult to design PRG constructions. - The construction of Chen and Tell composes two PRGs: G₁:{0,1}^{(1+o(1)) ⋅ log m} → {0,1}^{r₂ = m^{Ω(1)}} and G₂:{0,1}^{r₂} → {0,1}^m. The first PRG is constructed from the extreme high-end hardness assumption, and the second PRG needs to run in time m^{1+o(1)}, and is constructed assuming one way functions. We show that in black-box proofs of hardness amplification to 1/2+1/m, reductions must make Ω(m) queries, even in the extreme high-end. Known PRG constructions from hard functions are black-box and use (or imply) hardness amplification, and so cannot be used to construct a PRG G₂ from the extreme high-end hardness assumption. The new feature of our hardness amplification result is that it applies even to the extreme high-end setting of parameters, whereas past work does not. Our techniques also improve recent lower bounds of Ron-Zewi, Shaltiel and Varma (ITCS 2021) on the number of queries of local list-decoding algorithms.

Recently several conjectures were made regarding the Fourier spectrum of low-degree polynomials. We show that these conjectures imply new correlation bounds for functions related to Majority. Then we prove several new results on correlation bounds which aim to, but don't, resolve the conjectures. In particular, we prove several new results on Majority which are of independent interest and complement Smolensky’s classic result.

Motivated by storage applications, we study the following data structure problem: an encoder wishes to store a collection of jointly-distributed files : = (X1, X2, …, Xn) ∼ µ which are correlated (Hµ ≤ Σi Hµ(Xi)), using as little (expected) memory as possible, such that each individual file Xi can be recovered quickly with few (ideally constant) memory accesses. In the case of independent random files, a dramatic result by Pǎtraşcu (FOCS’08) and subsequently by Dodis, Pǎtraşcu and Thorup (STOC’10) shows that it is possible to store using just a constant number of extra bits beyond the information-theoretic minimum space, while at the same time decoding each Xi in constant time. However, in the (realistic) case where the files are correlated, much weaker results are known, requiring at least Ω(n/poly lg n) extra bits for constant decoding time, even for “simple” joint distributions µ. We focus on the natural case of compressing Markov chains, i.e., storing a length-n random walk on any (possibly directed) graph G. Denoting by κ(G, n) the number of length-n walks on G, we show that there is a succinct data structure storing a random walk using lg2 κ(G, n) + O(lg n) bits of space, such that any vertex along the walk can be decoded in O(1) time on a word-RAM. If the graph is strongly connected (e.g., undirected), the space can be improved to only lg2 k(G, n) + 5 extra bits. For the harder task of matching the point-wise optimal space of the walk, i.e., the empirical entropy , we present a data structure with O(1) extra bits at the price of O(lg n) decoding time, and show that any improvement on this would lead to an improved solution on the long-standing Dictionary problem. All of our data structures support the online version of the problem with constant update and query time.

We show that for every small AC$^{0}$ circuit $C:\{0,1\}^{\ell}\to\{0,1\}^{m}$ there exists a multiset $S$ of $2^{m-m^{\Omega(1)}}$ restrictions that preserve the output distribution of $C$ and, moreover, polarize min-entropy: the restriction of $C$ to any $r\in S$ either is constant or has polynomial min-entropy. This structural result is then applied to exhibit an explicit boolean function $h:\{0,1\}^{n}\to\{0,1\}$ such that for every small AC$^{0}$ circuit $C:\{0,1\}^{\ell}\to\{0,1\}^{n+1}$ the output distribution of $C$ for a uniform input has statistical distance exponentially close to $1/2$ from the distribution $(U,h(U))$ for $U$ uniform in $\{0,1\}^{n}$. Previous such “sampling lower bounds” either gave exponentially small statistical distance or applied to functions $h$ with large output length. We also show that the output distribution of a $d$-local map $f:[n]^{\ell}\to[n]^{n}$ for a uniform input has statistical distance at least $1-2\cdot\exp(-n/\log^{\exp(O(d))}n)$ from a uniform permutation of $[n]$. Here $d$-local means that each output symbol in $[n]=\{1,2,\ldots,n\}$ depends only on $d$ of the $\ell$ input symbols in $[n]$. This separates AC$^{0}$ sampling from local, because small AC$^{0}$ circuits can sample almost uniform permutations. As an application, we prove that any cell-probe data structure for storing permutations $\pi$ of $n$ elements such that $\pi(i)$ can be retrieved with $d$ nonadaptive probes must use space $\ge\log_{2}n!+n/\log^{\exp(O(d))}n$.

Let $G$ be the special linear group ${SL}(2,q)$. We show that if $(a_1,\ldots,a_t)$ and $(b_1,\ldots,b_t)$ are sampled uniformly from large subsets $A$ and $B$ of $G^t$, then their interleaved product $a_1 b_1 a_2 b_2 \cdots a_t b_t$ is nearly uniform over $G$. This extends a result of the first author [W. T. Gowers, Combin. Probab. Comput., 17 (2008), pp. 363--387], which corresponds to the independent case where $A$ and $B$ are product sets. We obtain a number of other results. For example, we show that if $X$ is a probability distribution on $G^m$ such that any two coordinates are uniform in $G^2$, then a pointwise product of $s$ independent copies of $X$ is nearly uniform in $G^m$, where $s$ depends on $m$ only. Extensions to other groups are also discussed. We obtain closely related results in communication complexity, which is the setting where some of these questions were first asked by Miles and Viola [ Shielding circuits with groups, in ACM Symposium on the Theory of Computing (STOC), ACM, New York, 2013, pp. 251--260]. For example, suppose party $A_i$ of $k$ parties $A_1,\dots,A_k$ receives on its forehead a $t$-tuple $(a_{i1},\dots,a_{it})$ of elements from $G$. The parties are promised that the interleaved product $a_{11}\dots a_{k1}a_{12}\dots a_{k2}\dots a_{1t}\dots a_{kt}$ is equal either to the identity $e$ or to some other fixed element $g\in G$, and their goal is to determine which of the two the product is equal to. We show that for all fixed $k$ and all sufficiently large $t$ the communication is $\Omega(t \log |G|)$, which is tight. Even for $k=2$ the previous best lower bound was $\Omega(t)$. As an application, we establish the security of the leakage-resilient circuits studied by Miles and Viola [ Shielding circuits with groups, in ACM Symposium on the Theory of Computing (STOC), ACM, New York, 2013, pp. 251--260] in the “only computation leaks” model.

We study how well can q-query decision trees distinguish between the following two distributions: (i) R = (R1,...,RN) that are i.i.d. indicator random variables, (ii) X=(R|R ϵ A) where A is an event s.t. Pr[R ϵ A] ≥ 2-a. We prove two lemmas: · Forbidden-set lemma: There exists B ⊆ [N] of size poly(a, q, 1/η) such that q-query trees that do not query variables in B cannot distinguish X from R with advantage η. · Fixed-set lemma: There exists B ⊆ [N] of size poly(a, q,1/η) and v ϵ0,1Bsuch that q-query trees do not distinguish (X|XB=v) from (R|RB=v) with advantage η. The first can be seen as an extension of past work by Edmonds, Impagliazzo, Rudich and Sgall (Computational Complexity 2001), Raz (SICOMP 1998), and Shaltiel and Viola (SICOMP 2010) to adaptive decision trees. It is independent of recent work by Meir and Wigderson (ECCC 2017) bounding the number of i ϵ [N] for which there exists a q-query tree that predicts Xifrom the other bits. We use the second, fixed-set lemma to prove lower bounds on black-box proofs for hardness amplification that amplify hardness from δ to 1/2-ϵ. Specifically: · Reductions must make q=Ω(log(1/δ)/ϵ2) queries, implying a "size loss factor" of q. We also prove the lower bound q=Ω(log(1/δ)/ϵ) for "error-less" hardness amplification proofs, and for direct-product lemmas. These bounds are tight. · Reductions can be used to compute Majority on Ω(1/ϵ) bits, implying that black box proofs cannot amplify hardness of functions that are hard against constant depth circuits (unless they are allowed to use Majority gates). Both items extend to pseudorandom-generator constructions. These results prove 15-year-old conjectures by Viola, and improve on three incomparable previous works (Shaltiel and Viola, SICOMP 2010; Gutfreund and Rothblum, RANDOM 2008; Artemenko and Shaltiel, Computational Complexity 2014).

We revisit one of the classic problems in the data stream literature, namely, that of estimating the frequency moments $F_p$ for $0 < p < 2$ of an underlying $n$-dimensional vector presented as a sequence of additive updates in a stream. It is well-known that using $p$-stable distributions one can approximate any of these moments up to a multiplicative $(1+ε)$-factor using $O(ε^{-2} \log n)$ bits of space, and this space bound is optimal up to a constant factor in the turnstile streaming model. We show that surprisingly, if one instead considers the popular random-order model of insertion-only streams, in which the updates to the underlying vector arrive in a random order, then one can beat this space bound and achieve $\tilde{O}(ε^{-2} + \log n)$ bits of space, where the $\tilde{O}$ hides poly$(\log(1/ε) + \log \log n)$ factors. If $ε^{-2} \approx \log n$, this represents a roughly quadratic improvement in the space achievable in turnstile streams. Our algorithm is in fact deterministic, and we show our space bound is optimal up to poly$(\log(1/ε) + \log \log n)$ factors for deterministic algorithms in the random order model. We also obtain a similar improvement in space for $p = 2$ whenever $F_2 \gtrsim \log n\cdot F_1$.

Let $D$ be a $b$-wise independent distribution over $\{0,1\}^m$. Let $E$ be the “noise” distribution over $\{0,1\}^m$ where the bits are independent and each bit is 1 with probability $\eta/2$. We study which tests $f \colon \{0,1\}^m \to [-1,1]$ are $\varepsilon$-fooled by $D+E$, i.e., $|{\rm E}[f(D+E)] - {\rm E}[f(U)]| \le \varepsilon$, where $U$ is the uniform distribution. We show that $D+E$ $\varepsilon$-fools product tests $f : (\{0,1\}^n)^k \to [-1,1]$ given by the product of $k$ bounded functions on disjoint $n$-bit inputs with error $\varepsilon = k(1-\eta)^{\Omega(b^2/m)}$, where $m = nk$ and $b \ge n$. This bound is tight when $b = \Omega(m)$ and $\eta \ge (\log k)/m$. For $b \ge m^{2/3} \log m$ and any constant $\eta$ the distribution $D+E$ also $0.1$-fools log-space algorithms. We develop two applications of this type of results. First, we prove communication lower bounds for decoding noisy codewords of length $m$ split among $k$ parties. For Reed--Solomon codes of dimension $m/k$ where $k = O(1)$, communication $\Omega(\eta m) - O(\log m)$ is required to decode one message symbol from a codeword with $\eta m$ errors, and communication $O(\eta m \log m)$ suffices. Second, we obtain pseudorandom generators. We can $\varepsilon$-fool product tests $f\colon (\{0,1\}^n)^k \to [-1,1]$ under any permutation of the bits with seed lengths $2n + \tilde O(k^2 \log (1/\varepsilon))$ and $O(n) + \tilde O(\sqrt{nk \log 1/\varepsilon})$. Previous generators have seed lengths $\ge nk/2$ or $\ge n \sqrt{n k}$. For the special case where the $k$ bounded functions have range $\{0,1\}$ the previous generators have seed length $\ge (n+\log k)\log (1/\varepsilon)$.

Let k = k(n) be the largest integer such that there exists a k-wise uniform distribution over {0,1}^n that is supported on the set S_m := {x in {0,1}^n: sum_i x_i equiv 0 mod m}, where m is any integer. We show that Omega(n/m^2 log m) <= k <= 2n/m + 2. For k = O(n/m) we also show that any k-wise uniform distribution puts probability mass at most 1/m + 1/100 over S_m. For any fixed odd m there is k \ge (1 - Omega(1))n such that any k-wise uniform distribution lands in S_m with probability exponentially close to |S_m|/2^n; and this result is false for any even m.

Party Aiof k parties A1,...,Akreceives on its forehead a t-tuple (ai1,...,ait) of elements from the group G = SL(2, q). The parties are promised that the interleaved product a11...ak1a12...ak2...a1t...aktis equal either to the identity e or to some other fixed element g ∈ G. Their goal is to determine which of e and g the interleaved product is equal to, using the least amount of communication. We show that for all fixed k and all sufficiently large t the communication is Ω(t log |G|), which is tight. As an application, we establish the security of the leakage-resilient circuits studied by Miles and Viola (STOC 2013) in the "only computation leaks" model. Our main technical contribution is of independent interest. We show that if X is a probability distribution on Gmsuch that any two coordinates are uniform in G2, then a pointwise product of s independent copies of X is nearly uniform in Gm, where s depends on m only.

We consider randomness extraction by AC0 circuits. The main parameter, n, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound k=k(n), the seed length r=r(n), the output length m=m(n), and the (output) deviation bound epsilon=epsilon(n). For k <=e n/\log^(omega(1))(n), we show that AC0-extraction is possible if and only if m/r <= 1+ poly(log(n)) * k/n; that is, the extraction rate m/r exceeds the trivial rate (of one) by an additive amount that is proportional to the min-entropy rate k/n. In particular, non-trivial AC0-extraction (i.e., m >= r+1) is possible if and only if k * r > n/poly(log(n)). For k >= n/log^(O(1))(n), we show that AC0-extraction of r+Omega(r) bits is possible when r=O(log(n)), but leave open the question of whether more bits can be extracted in this case. The impossibility result is for constant epsilon, and the possibility result supports epsilon=1/poly(n). The impossibility result is for (possibly) non-uniform AC0, whereas the possibility result hold for uniform AC0. All our impossibility results hold even for the model of bit-fixing sources, where k coincides with the number of non-fixed (i.e., random) bits. We also consider deterministic AC0 extraction from various classes of restricted sources. In particular, for any constant $\delta>0$, we give explicit AC0 extractors for poly(1/delta) independent sources that are each of min-entropy rate delta; and four sources suffice for delta=0.99. Also, we give non-explicit AC0 extractors for bit-fixing sources of entropy rate 1/poly(log(n)) (i.e., having n/poly(log(n)) unfixed bits). This shows that the known analysis of the "restriction method" (for making a circuit constant by fixing as few variables as possible) is tight for AC0 even if the restriction is picked deterministically depending on the circuit.

Alice receives a tuple (a1,...,at) of t elements from the group G = SL(2,q). Bob similarly receives a tuple of t elements (b1,...,bt). They are promised that the interleaved product prodi ≤ t ai bi equals to either g and h, for two fixed elements g,h ∈ G. Their task is to decide which is the case.

This article takes a new step towards closing the gap between pseudorandom functions (PRF) and their popular, bounded-input-length counterparts. This gap is both quantitative, because these counterparts are more efficient than PRF in various ways, and methodological, because these counterparts usually fit in the substitution-permutation network paradigm (SPN), which has not been used to construct PRF. We give several candidate PRF F i that are inspired by the SPN paradigm. Most of our candidates are more efficient than previous ones. Our main candidates are as follows. — F 1 : {0,1} n → {0,1} n is an SPN whose S-box is a random function on b bits given as part of the seed. We prove that F 1 resists attacks that run in time ≤ 2 ϵb . — F 2 : {0,1} n → {0,1} n is an SPN where the S-box is (patched) field inversion, a common choice in practical constructions. We show that F 2 is computable with boolean circuits of size n ⋅ log O (1) n and that it has exponential security 2 Ω( n ) against linear and differential cryptanalysis. — F 3 : {0,1} n → {0,1} is a nonstandard variant on the SPN paradigm, where “states” grow in length. We show that F 3 is computable with TC 0 circuits of size n 1 + ϵ , for any ϵ > 0, and that it is almost 3-wise independent. — F 4 : {0,1} n → {0,1} uses an extreme setting of the SPN parameters (one round, one S-box, no diffusion matrix). The S-box is again (patched) field inversion. We show that F 4 is computable by circuits of size n ⋅ log O (1) n and that it fools all parity tests on ≤2 0.9 n outputs. Assuming the security of our candidates, our work narrows the gap between the Natural Proofs barrier and existing lower bounds in three models: circuits, TC 0 circuits, and Turing machines.

We show that the promise problem of distinguishing n-bit strings of relative Hamming weight $${1/2 + \Omega(1/{\rm lg}^{d-1} n)}$$ from strings of weight $${1/2 - \Omega(1/{\rm \lg}^{d - 1} n)}$$ can be solved by explicit, randomized (unbounded fan-in) poly(n)-size depth-d circuits with error $${\leq 1/3}$$ , but cannot be solved by deterministic poly(n)-size depth-(d+1) circuits, for every $${d \geq 2}$$ ; and the depth of both is tight. Our bounds match Ajtai’s simulation of randomized depth-d circuits by deterministic depth-(d + 2) circuits (Ann. Pure Appl. Logic; ’83) and provide an example where randomization buys resources. To rule out deterministic circuits, we combine Håstad’s switching lemma with an earlier depth-3 lower bound by the author (Computational Complexity 2009). To exhibit randomized circuits, we combine recent analyses by Amano (ICALP ’09) and Brody and Verbin (FOCS ’10) with derandomization. To make these circuits explicit, we construct a new, simple pseudorandom generator that fools tests $${A_1 \times A_2 \times \cdots \times A_{{\rm lg}{n}}}$$ for $${A_i \subseteq [n], |A_{i}| = n/2}$$ with error 1/n and seed length O(lg n), improving on the seed length $${\Omega({\rm lg}\, n\, {\rm lg}\, {\rm lg}\, n)}$$ of previous constructions.

We study how to spread k tokens of information to every node on an n-node dynamic network, the edges of which are changing at each round. This basic gossip problem can be completed in O(n + k) rounds in any static network, and determining its complexity in dynamic networks is central to understanding the algorithmic limits and capabilities of various dynamic network models. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying and forwarding them. We first consider the strongly adaptive adversary model where in each round, each node first chooses a token to broadcast to all its neighbors (without knowing who they are), and then an adversary chooses an arbitrary connected communication network for that round with the knowledge of the tokens chosen by each node. We show that Ω(nk/log n + n) rounds are needed for any randomized (centralized or distributed) token-forwarding algorithm to disseminate the k tokens, thus resolving an open problem raised in [KLO10]. The bound applies to a wide class of initial token distributions, including those in which each token is held by exactly one node and well-mixed ones in which each node has each token independently with a constant probability. Our result for the strongly adaptive adversary model motivates us to study the weakly adaptive adversary model where in each round, the adversary is required to lay down the network first, and then each node sends a possibly distinct token to each of its neighbors. We propose a simple randomized distributed algorithm where in each round, along every edge (u, v), a token sampled uniformly at random from the symmetric difference of the sets of tokens held by node u and node v is exchanged. We prove that starting from any well-mixed distribution of tokens where each node has each token independently with a constant probability, this algorithm solves the k-gossip problem in O((n + k) log n log k) rounds with high probability over the initial token distribution and the randomness of the protocol. We then show how the above uniform sampling problem can be solved using Õ(log n) bits of communication, making the overall algorithm communication-efficient. We next present a centralized algorithm that solves the gossip problem for every initial distribution in O((n + k) log2 n) rounds in the offline setting where the entire sequence of communication networks is known to the algorithm in advance. Finally, we present an -round centralized offline algorithm in which each node can only broadcast a single token to all of its neighbors in each round.

Suppose each of k ≤ no(1) players holds an n-bit number xi in its hand. The players wish to determine if σi ≤ k xi = s. We give a public-coin protocol with error 1% and communication O(k lg k). The communication bound is independent of n, and for k ≥ 3 improves on the O(k lg n) bound by Nisan (Bolyai Soc. Math. Studies; 1993). Our protocol also applies to addition modulo m. In this case we give a matching (public-coin) Ω(k lg k) lower bound for various m. We also obtain some lower bounds over the integers, including Ω(k lg lg k) for protocols that are one-way, like ours. We give a protocol to determine if σ xi > s with error 1% and communication O(k lg k)lgn. For k ≥ 3 this improves on Nisan's O(k lg2 n) bound. A similar improvement holds for computing degree-(k − 1) polynomial-threshold functions in the number-on-forehead model. We give a (public-coin, 2-player, tight) Ω(lg n) lower bound to determine if x1 > x2. This improves on the bound by Smirnov (1988). As an application, we show that polynomial-size AC0 circuits augmented with O(1) threshold (or symmetric) gates cannot compute cryptographic pseudorandom functions, extending the result about AC0 by Linial, Mansour, and Nisan (J. ACM; 1993).

We show how to efficiently compile any given circuit C into a leakage-resistant circuit C' such that any function on the wires of C' that leaks information during a computation C'(x) yields advantage in computing the product of |C'|Ω(1) elements of the alternating group Au. In combination with new compression bounds for Au products, also obtained here, C' withstands leakage from virtually any class of functions against which average-case lower bounds are known. This includes communication protocols, and AC0 circuits augmented with few arbitrary symmetric gates. If NC1 ' TC0 then then the construction resists TC0 leakage as well. We also conjecture that our construction resists NC1 leakage. In addition, we extend the construction to the multi-query setting by relying on a simple secure hardware component. We build on Barrington's theorem [JCSS '89] and on the previous leakage-resistant constructions by Ishai et al. [Crypto '03] and Faust et al. [Eurocrypt '10]. Our construction exploits properties of Au beyond what is sufficient for Barrington's theorem.

We bound the minimum number$w$of wires needed to compute any (asymptotically good) error-correcting code$C:\{0,1\}^{\Omega (n)}\to\{0,1\}^{n}$with minimum distance$\Omega (n)$, using unbounded fan-in circuits of depth$d$with arbitrary gates. Our main results are: 1) if$d=2$, then$w=\Theta (n ({\lg n/\lg\lg n})^{2})$; 2) if$d=3$, then$w=\Theta (n\lg\lg n)$; 3) if$d=2k$or$d=2k+1$for some integer$k\geq 2$, then$w=\Theta (n\lambda_{k}(n))$, where$\lambda_{1}(n)=\lceil\lg n\rceil$,$\lambda_{i+1}(n)=\lambda_{i}^{\ast}(n)$, and the$\ast$operation gives how many times one has to iterate the function$\lambda_{i}$to reach a value at most 1 from the argument$n$; and 4) if$d=\lg^{\ast}n$, then$w=O(n)$. For depth$d=2$, our$\Omega (n ({\lg n/\lg\lg n})^{2})$lower bound gives the largest known lower bound for computing any linear map. The upper bounds imply that a (necessarily dense) generator matrix for our code can be written as the product of two sparse matrices. Using known techniques, we also obtain similar (but not tight) bounds for computing pairwise-independent hash functions. Our lower bounds are based on a superconcentrator-like condition that the graphs of circuits computing good codes must satisfy. This condition is provably intermediate between superconcentrators and their weakenings considered before.

The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor k equal to the bit-length of the distributions: ε-distinguishability implies ε/k-predictability. This paper studies the consequences of avoiding this loss - what we call "beating the hybrid argument" -- and develops new proof techniques that circumvent the loss in certain natural settings. Specifically, we obtain the following results:

We bound the minimum number w of wires needed to compute any (asymptotically good) error-correcting code C:{0,1}Ω(n) -> {0,1}n with minimum distance Ω(n), using unbounded fan-in circuits of depth d with arbitrary gates. Our main results are: (1) If d=2 then w = Θ(n ({log n/ log log n})2). (2) If d=3 then w = Θ(n lg lg n). (3) If d=2k or d=2k+1 for some integer k ≥ 2 then w = Θ(n λk(n)), where λ1(n)=⌈ log n⌉, λi+1(n)= λi*(n), and the * operation gives how many times one has to iterate the function λi to reach a value at most 1 from the argument n. (4) If d=log* n then w=O(n).

We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a. AC0) circuit, and (ii) the uniform distribution over any code that is ``good'', i.e. has constant relative distance and rate. This seems to be the first lower bound of this kind. We give two simple applications of this result: (1) any data structure for storing codewords of a good code requires an additive logarithmic redundancy, if each bit of the codeword can be retrieved by a small AC0 circuit; (2) for some choice of the underlying combinatorial designs, the output distribution of Nisan's pseudorandom generator against AC0 circuits of depth d cannot be sampled by small AC0 circuits of depth less than d.

Complexity theory typically studies the complexity of computing a function $h(x) : \{0, 1\}^m \to \{0, 1\}^n$ of a given input x. A few works have suggested studying the complexity of generating—or sampling—the distribution $h(x)$ for uniform x, given random bits. We further advocate this study, with a new emphasis on lower bounds for restricted computational models. Our main results are the following: (1) Any function $f : \{0, 1\}^\ell \to \{0, 1\}^n$ such that (i) each output bit $f_i$ depends on $o(\log n)$ input bits, and (ii) $\ell \le \log_2 \binom{n}{\alpha n} + n^{0.99}$ has output distribution $f(U)$ at statistical distance $\ge 1 - 1/n^{0.49}$ from the uniform distribution over n-bit strings of hamming weight $\alpha n$. We also prove lower bounds for generating $(X,b(X))$ for Boolean b, and in the case in which each bit $f_i$ is a small-depth decision tree. These lower bounds seem to be the first of their kind; the proofs use anticoncentration results for the sum of random variables. (2) Lower bounds for succinct data structures. As a corollary of (1), we obtain the first lower bound for the membership problem of representing a set $S \subseteq [n]$ of size $\alpha n$, in the case where $1/\alpha$ is a power of 2: If queries “$i \in S$?” are answered by nonadaptively probing $o(\log n)$ bits, then the representation uses $\ge \log_2 \binom{n}{\alpha n} + \Omega(\log n)$ bits. (3) Upper bounds complementing the bounds in (1) for various settings of parameters. (4) Uniform randomized $\mathrm{AC}^0$ circuits of $\mathrm{poly}(n)$ size and depth $d = O(1)$ with error $\epsilon$ can be simulated by uniform randomized $\mathrm{AC}^0$ circuits of $\mathrm{poly}(n)$ size and depth $d+1$ with error $\epsilon + o(1)$ using $\le (\log n)^{O( \log \log n)}$ random bits. Previous derandomizations [M. Ajtai and A. Wigderson, Adv. Comput. Res., 5 (1989), pp. 199–223], [N. Nisan, Combinatorica, 11 (1991), pp. 63–70] increase the depth by a constant factor, or else have poor seed length.

We prove lower bounds on the redundancy necessary to represent a set $S$ of objects using a number of bits close to the information-theoretic minimum $\log_2 |S|$, while answering various queries by probing few bits. Our main results are as follows: (i) To represent $n$ ternary values $t \in \{0,1,2\}^n$ in terms of $u$ bits $b \in \{0, 1\}^u$ while accessing a single value $t_i \in \{0,1,2\}$ by probing $q$ bits of $b$, one needs $u \geq (\log_2 3)n + n/2^{O(q)}$. This matches an exciting representation by Pǎtraşcu (FOCS 2008), later refined with Dodis and Thorup (STOC 2010), where $u \leq (\log_2 3)n + n/2^{\Omega(q)}$. We also note that results on logarithmic forms imply the lower bound $u \geq (\log_2 3)n + n/\log^{O(1)} n$ if we access $t_i$ by probing one cell of $\log n$ bits. (ii) To represent sets of size $n/3$ from a universe of $n$ elements in terms of $u$ bits $b \in \{0, 1\}^u$ while answering membership queries by probing $q$ bits of $b$, one needs $u \geq \log_2 \binom{n}{n/3} + n/2^{O(q)} - \log n$. Both results hold even if the probe locations are determined adaptively. Ours are the first lower bounds for these fundamental problems; we obtain them by drawing on ideas used in a lower bound for locally decodable codes by Shaltiel and the author [SIAM J. Comput., 39 (2010), pp. 3122--3154].

We obtain the first deterministic extractors for sources generated (or sampled) by small circuits of bounded depth. Our main results are (1) we extract $k (k/nd)^{O(1)}$ bits with exponentially small error from $n$-bit sources of min-entropy $k$ that are generated by functions $f : \{0, 1\}^\ell \to \{0, 1\}^n$, where each output bit depends on $\le d$ input bits. In particular, we extract from $\mathrm{NC}^0$ sources, corresponding to $d = O(1)$; (2) we extract $k (k/n^{1+\gamma})^{O(1)}$ bits with superpolynomially small error from $n$-bit sources of min-entropy $k$ that are generated by $\mathrm{poly}(n)$-size $\mathrm{AC}^0$ circuits, for any $\gamma > 0$. As our starting point, we revisit the connection by Trevisan and Vadhan [IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2000, pp. 32--42] between circuit lower bounds and extractors for sources generated by circuits. We note that such extractors (with very weak parameters) are equivalent to lower bounds for generating distributions [E. Viola, SIAM J. Comput., 41 (2012), pp. 191--218; S. Lovett and E. Viola, Comput. Complexity, 21 (2012), pp. 245--256]. Building on those bounds, we prove that the sources in (1) and (2) are (close to) a convex combination of high-entropy “bit-block” sources. Introduced here, such sources are a special case of affine ones. As extractors for (1) and (2) one can use the extractor for low-weight affine sources by Rao [IEEE Conference on Computational Complexity, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 95--101]. Along the way, we exhibit an explicit boolean function $b : \{0, 1\}^n \to \{0, 1\}$ such that $\mathrm{poly}(n)$-size $\mathrm{AC}^0$ circuits cannot generate the distribution $(Y,b(Y))$, solving a problem about the complexity of distributions. Independently, De and Watson [ACM Trans. Comput. Theory, 4 (2012), 3] obtain a result similar to (1) in the special case $d = o(\lg n)$.

This special section comprises eight fully refereed papers whose extended abstracts were presented at the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008) in Philadelphia, Pennsylvania, October 26–28, 2008. The unrefereed conference versions of these papers were published by IEEE in the FOCS 2008 proceedings. The regular conference program consisted of 79 papers chosen from among 276 submissions. These were selected by a program committee consisting of Scott Aaronson, Yossi Azar, Avrim Blum, Harry Buhrman, Artur Czumaj, Yevgeniy Dodis, David Eppstein, Jeff Erickson, Naveen Garg, Tom Hayes, Sampath Kannan, Jonathan Katz, Valerie King, Mohammad Mahdian, Yury Makarychev, Yishay Mansour, Rafail Ostrovsky, Toniann Pitassi, Harald Raecke, R. Ravi (chair), Madhu Sudan, and Emanuele Viola. The papers invited to this special section were also selected with the input of the program committee. The eight papers in this section span a broad range of topics, including algorithmic game theory, computational complexity, hardness of approximation, learning theory, pseudorandomness, and quantum algorithms. Each paper underwent an extensive refereeing process; we thank both the authors and the anonymous referees for their efforts. In addition, we would like to thank Eva Tardos, who was SICOMP's editor-in-chief as this project began, and SIAM staff member Cherie Trebisky for their help in preparing this special section.

Complexity theory typically studies the complexity of computing a function h(x) : {0, 1}m→ {0,1}nof a given input x. We advocate the study of the complexity of generating the distribution h(x) for uniform x, given random bits. Our main results are: (1) Any function f : {0, 1}ℓ→ {0,1}nsuch that (i) each output bit fidepends on o(log n) input bits, and (ii) ℓ ≤ log2(αnn) + n0.99, has output distribution f(U) at statistical distance ≥ 1 - 1/n0.49from the uniform distribution over n-bit strings of hamming weight αn. We also prove lower bounds for generating (X, b(X)) for boolean b, and in the case in which each bit fiis a small-depth decision tree. These lower bounds seem to be the first of their kind; the proofs use anti-concentration results for the sum of random variables. (2) Lower bounds for generating distributions imply succinct data structures lower bounds. As a corollary of (1), we obtain the first lower bound for the membership problem of representing a set S ⊆ [n] of size αn, in the case where 1/α is a power of 2: If queries "i ∈ S?" are answered by non-adaptively probing o(log n) bits, then the representation uses ≥ log2(αn3) + Ω(log n) bits. (3) Upper bounds complementing the bounds in (1) for various settings of parameters. (4) Uniform randomized AC0circuits of poly(n) size and depth d = O(1) with error ϵ can be simulated by uniform randomized AC0circuits of poly(n) size and depth d + 1 with error ϵ + o(1) using ≤ (log n)O(log log n)random bits. Previous derandomizations [Ajtai and Wigderson '85; Nisan '91] increase the depth by a constant factor, or else have poor seed length.

The partial sums problem in succinct data structures asks to preprocess an array A[1 ‥ n] of bits into a data structure using as close to n bits as possible, and answer queries of the form . The problem has been intensely studied, and features as a subroutine in a number of succinct data structures. We show that, if we answer Rank(k) queries by probing t cells of w bits, then the space of the data structure must be at least n + n/wO(t) bits. This redundancy/probe trade-off is essentially optimal: Patrascu [FOCS'08] showed how to achieve n + n/(w/t)Ω(t) bits. We also extend our lower bound to the closely related Select queries, and to the case of sparse arrays.

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G:\mathbb{F}^s\to\mathbb{F}^n$ that fool polynomials over a finite field $\mathbb{F}$: We stress that the results in (1) and (2) are unconditional, i.e., do not rely on any unproven assumption. Moreover, the results in (3) rely on a special case of the conjecture which may be easier to prove. Our generator for degree-d polynomials is the componentwise sum of d generators for degree-1 polynomials (on independent seeds). Prior to our work, generators with logarithmic seed length were only known for degree-1 (i.e., linear) polynomials [J. Naor and M. Naor, SIAM J. Comput., 22 (1993), pp. 838–856]. In fact, over small fields such as $\mathbb{F}_2=\{0,1\}$, our results constitute the first progress on these problems since the long-standing generator by Luby, Veličković, and Wigderson [Deterministic approximate counting of depth-2 circuits, in Proceedings of the 2nd Israeli Symposium on Theoretical Computer Science (ISTCS), 1993, pp. 18–24], whose seed length is much bigger: $s=\exp\left(\Omega\left(\sqrt{\log n}\right)\right)$, even for the case of degree-2 polynomials over $\mathbb{F}_2$.

We show that any distribution on $\{-1,+1\}^n$ that is k-wise independent fools any halfspace (or linear threshold function) $h:\{-1,+1\}^n\to\{-1,+1\}$, i.e., any function of the form $h(x)=\operatorname{sign}(\sum_{i=1}^{n}w_{i}x_{i}-\theta)$, where the $w_1,\dots,w_n$ and $\theta$ are arbitrary real numbers, with error $\epsilon$ for $k=O(\epsilon^{-2}\log^2(1/\epsilon))$. Our result is tight up to $\log(1/\epsilon)$ factors. Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators $G:\{-1,+1\}^s\to\{-1,+1\}^n$ that fool halfspaces. Specifically, we fool halfspaces with error $\epsilon$ and seed length $s=k\cdot\log n=O(\log n\cdot\epsilon^{-2}\log^2(1/\epsilon))$. Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio [Comput. Complexity, 16 (2007), pp. 180–209].

Hardness amplification is the fundamental task of converting a $\delta$-hard function $f:\{0,1\}^n\to\{0,1\}$ into a $(1/2-\epsilon)$-hard function $\mathit{Amp}(f)$, where f is $\gamma$-hard if small circuits fail to compute f on at least a $\gamma$ fraction of the inputs. In this paper we study the complexity of black-box proofs of hardness amplification. A class of circuits $\mathcal{D}$ proves a hardness amplification result if for any function h that agrees with $\mathit{Amp}(f)$ on a $1/2+\epsilon$ fraction of the inputs there exists an oracle circuit $D\in\mathcal{D}$ such that $D^h$ agrees with f on a $1-\delta$ fraction of the inputs. We focus on the case where every $D\in\mathcal{D}$ makes nonadaptive queries to h. This setting captures most hardness amplification techniques. We prove two main results: (1) The circuits in $\mathcal{D}$ “can be used” to compute the majority function on $1/\epsilon$ bits. In particular, when $\epsilon\leq1/\log^{\omega(1)}n$, $\mathcal{D}$ cannot consist of oracle circuits that have unbounded fan-in, size $\mathrm{poly}(n)$, and depth $O(1)$. (2) The circuits in $\mathcal{D}$ must make $\Omega\left(\log(1/\delta)/\epsilon^2\right)$ oracle queries. Both our bounds on the depth and on the number of queries are tight up to constant factors. Our results explain why hardness amplification techniques have failed to transform known lower bounds against constant-depth circuit classes into strong average-case lower bounds. Our results reveal a contrast between Yao's XOR lemma ($\mathit{Amp}(f):=f(x_1)\oplus\cdots\oplus f(x_t)\in\{0,1\}$) and the direct-product lemma ($\mathit{Amp}(f):=f(x_1)\circ\cdots\circ f(x_t)\in\{0,1\}^t$; here $\mathit{Amp}(f)$ is non-Boolean). Our results (1) and (2) apply to Yao's XOR lemma, whereas known proofs of the direct-product lemma violate both (1) and (2). One of our contributions is a new technique for handling “nonuniform” reductions, i.e., the case when $\mathcal{D}$ contains many circuits.

We show that any distribution on {-1,+1}nthat is k-wise independent fools any halfspace (a.k.a. threshold) h : {-1,+1}n¿ {-1,+1}, i.e., any function of the form h(x) = sign(¿i=1nwiXi- ¿) where the w1,..., wn, ¿ are arbitrary real numbers, with error ¿ for k = O(¿-2log2(1/¿)). Our result is tight up to log(1/¿) factors. Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators G : {-1,+1}s¿ {-1,+1}nthat fool halfspaces. Specifically, we fool halfspaces with error e and seed length s = k · log n = O(log n · ¿-2log2(1/¿)). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Comput. Complexity 2007).

We prove lower bounds on the redundancy necessary to represent a set S of objects using a number of bits close to the information-theoretic minimum log2 |S|, while answering various queries by probing few bits. Our main results are: To represent n ternary values t ∈ {0,1,2}n in terms of u bits b ∈ {0,1}u while accessing a single value ti ∈ {0,1,2} by probing q bits of b, one needs u ≥ (log2 3)n + n/2O(q). This matches an exciting representation by Patrascu (FOCS 2008), later refined with Thorup, where u ≤ (log_2 3)n + n/2Ω(q). We also note that results on logarithmic forms imply the lower bound u ≥ (log2 3)n + n/logO(1) n if we access ti by probing one cell of log n bits. To represent sets of size n/3 from a universe of n elements in terms of u bits b ∈ {0,1}u while answering membership queries by probing q bits of b, one needs u ≥ log2 n/(n/3) + n/2O(q) - log n. Both results above hold even if the probe locations are determined adaptively. Ours are the first lower bounds for these fundamental problems; we obtain them drawing on ideas used in lower bounds for locally decodable codes.

We prove that the sum of d small-bias generators L : Fsrarr Fnfools degree-d polynomials in n variables over a prime field F, for any fixed degree d and field F, including F = F2= {0,1}. Our result improves on both the work by Bogdanov and Viola (FOCS '07) and the beautiful follow-up by Lovett (STOC '08). The first relies on a conjecture that turned out to be true only for some degrees and fields, while the latter considers the sum of2d small-bias generators (as opposed to d in our result). Our proof builds on and somewhat simplifies the arguments by Bogdanov and Viola (FOCS '07) and by Lovett (STOC '08). Its core is a case analysis based on the bias of the polynomial to befooled.

We prove new results on the circuit complexity of approximate majority, which is the problem of computing majority of a given bit string whose fraction of 1's is bounded away from 1/2 (by a constant). We then apply these results to obtain new relationships between probabilistic time, BPTime (t), and alternating time, SigmaO(1)Time (t).

This paper presents a unified and simple treatment of basic questions concerning two computational models: multiparty communication complexity and GF(2) polynomials. The key is the use of (known) norms on Boolean functions, which capture their approximability in each of these models. The main contributions are new XOR lemmas. We show that if a Boolean function has correlation at most epsi les 1/2 with any of these models, then the correlation of the parity of its values on m independent instances drops exponentially with m. More specifically: For GF(2) polynomials of degree d, the correlation drops to exp (-m/4d). No XOR lemma was known even for d = 2. For c-bit k-party protocols, the correlation drops to 2cldrepsim/2k. No XOR lemma was known for k ges 3 parties. Another contribution in this paper is a general derivation of direct product lemmas from XOR lemmas. In particular, assuming that f has correlation at most epsi les 1/2 with any of the above models, we obtain the following bounds on the probability of computing m independent instances of f correctly: For GF(2) polynomials of degree d we again obtain a bound of exp(-m/4d). For c-bit k-party protocols we obtain a bound of 2-Omega(m)in the special case when epsi les exp (-c ldr 2k). In this range of epsi, our bound improves on a direct product lemma for two-parties by Parnafes, Raz, and Wigderson (STOC '97). We also use the norms to give improved (or just simplified) lower bounds in these models. In particular we give a new proof that the Modmfunction on n bits, for odd m, has correlation at most exp(-n/4d) with degree-d GF(2) polynomials.

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators G : FsrarrFnthat fool polynomials over a prime field F: (1) a generator that fools degree-2 (i.e., quadratic) polynomials to within error 1/n, with seed length s = O(log n); (2) a generator that fools degree-3 (i.e., cubic) polynomials to within error epsiv, with seed length s = O(Iog|F|n) + f(epsiv, F) where f depends only on epsiv and F (not on n), (3) assuming the "Gowers inverse conjecture," for every d a generator that fools degree-d polynomials to within error epsiv, with seed length, s = O(dldrIog|F|n) + f(d, epsiv, F) where f depends only on d, epsiv, and F (not on n). We stress that the results in (1) and (2) are unconditional, i.e. do not rely on any unproven assumption. Moreover, the results in (3) rely on a special case of the conjecture which may be easier to prove. Our generator for degree-d polynomials is the component-wise sum of d generators for degree-l polynomials (on independent seeds). Prior to our work, generators with logarithmic seed length were only known for degree-1 (i.e., linear) polynomials (Naor and Naor; SIAM J. Comput., 1993). In fact, over small fields such as F2= {0,1}, our results constitute the first progress on these problems since the long-standing generator by Luby, Velickovic and Wigderson (ISTCS1993), whose seed length is much bigger: s = exp (Omega(radiclogn)), even for the case of degree-2 polynomials over F2.

In this paper we study the one-way multi-party communication model, in which even party speaks exactly once in its turn. For every fixed k, we prove a tight lower hound of Omega (n1/(k-1)) on the probabilistic communication complexity of pointer jumping in a k-layered tree, where the pointers of the i-lh layer reside on the forehead of the i-th party to speak. The lower bound remains nontrivial even for k = (log n)1/2-Omega(1)parties. Previous to our work a lower bound was known only for k = 3 , and in very restricted models for k > 3. Our results have the following consequences to other models and problems, extending previous work in several directions. The one-way model is strong enough to capture general (non one-wav) multi-party protocols of bounded rounds. Thus we generalize to this multi-party model results on two directions studied in the classical 2-party model. The first is a mund hierarchy: We give an exponential separation between the power of r and 2r rounds in general probabilistic k-party protocols, for any fixed k and r. The second is the relative power of determinism and nondeterminism: We prove an exponential separation between nondeterministic and deterministic communication complexity for general k-party protocols with r rounds, for anvfixed k, r. The pointer jumping function is weak enough to be a special case of the well-studied disjointness function. Thus we obtain a lower bound of Omega (n1/(k-1)) on the probabilistic complexity of k-set disjointness in the oneway model, which was known only for k = 3 parties. Our result also extends a similar lower bound for the weaker simultaneous model, in which parties simultaneously send one message to a referee. Finally, we infer an exponential separation between the power of different orders in which parties send messages in the one-way model, for every fixed k. Previous to our work such a separation was only known for k = 3. Our lower bound technique, which handles functions of high discrepancy, may be of independent interest. It provides a "party-elimination " induction, based on a restricted form of a direct-product result, specific to the pointer jumping function.

We exhibit an explicitly computable pseudorandom generator stretching l bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant‐depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g., PARITY, MAJORITY). This improves on a generator by Luby, Velickovic, and Wigderson [Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993, pp. 18–24] that achieves the same stretch but fools only circuits of depth 2 with one arbitrary symmetric gate at the top. Our generator fools a strictly richer class of circuits than Nisan’s generator for constant‐depth circuits (but Nisan’s generator has a much bigger stretch) [Combinatorica, 11 (1991), pp. 63–70]. In particular, we conclude that every function computable by uniform $\poly(n)$‐size probabilistic constant‐depth circuits with $O(\log n)$ arbitrary symmetric gates is in $\mathit{TIME}(2^{n^{o(1)}})$. This seems to be the richest probabilistic circuit class known to admit a subexponential derandomization. Our generator is obtained by constructing an explicit function $f : \zo^n \to \zo$ that is very hard on average for constant‐depth circuits of size $s(n) = n^{\Omega(\log n)}$ with $\log s(n)$ arbitrary symmetric gates, and plugging it into the Nisan–Wigderson pseudorandom generator construction [J. Comput. System Sci., 49 (1994), pp. 149–167]. The proof of the average‐case hardness of this function is a modification of arguments by Razborov and Wigderson [Inform. Process. Lett., 45 (1993), pp. 303–307] and Hansen and Miltersen [Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 3153, Springer‐Verlag, Berlin, 2004, pp. 334–345] and combines Håstad’s switching lemma [Computational Limitations of Small‐Depth Circuits, MIT Press, Cambridge, MA, 1987] with a multiparty communication complexity lower bound by Babai, Nisan, and Szegedy [J. Comput. System Sci., 45 (1992), pp. 204–232].

We revisit the problem of hardness amplification in $\mathcal{NP}$, as recently studied by O'Donnell [J. Comput. System Sci., 69 (2004), pp. 68-94]. We prove that if $\mathcal{NP}$ has a balanced function f such that any circuit of size $s(n)$ fails to compute f on a $1/\poly(n)$ fraction of inputs, then $\mathcal{NP}$ has a function $f'$ such that any circuit of size $s'(n)=s(\sqrt{n})^{\Omega(1)}$ fails to compute $f'$ on a $1/2 - 1/s'(n)$ fraction of inputs. In particular, \begin{enumerate} \item if $s(n)=n^{\omega(1)}$, we amplify to hardness $1/2-1/n^{\omega(1)}$; \item if $s(n)=2^{n^{\Omega(1)}}$, we amplify to hardness $1/2-1/2^{n^{\Omega(1)}}$; \item if $s(n)=2^{\Omega(n)}$, we amplify to hardness $1/2-1/2^{\Omega(\sqrt{n})}$. \end{enumerate} Our results improve those of of O'Donnell, which amplify to $1/2-1/\sqrt{n}$. O'Donnell also proved that no construction of a certain general form could amplify beyond $1/2-1/n$. We bypass this barrier by using both derandomization and nondeterminism in the construction of $f'$. We also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that f is balanced are necessary for "black-box" hardness amplification procedures (such as ours).

We study pseudorandom generator (PRG) constructions G/sup f/ : {0, 1}/sup l/ /spl rarr/ {0, 1}/sup 1+s/ from one-way functions f : {0, 1}/sup n/ /spl rarr/ {0, 1}/sup m/. We consider PRG constructions of the form G/sup f/ (x) = C(f(q/sub 1/) ...f (g/sub poly(n)/)) where C is a polynomial-size constant depth circuit (i.e., AC/sup 0/) and C and the q's are generated from x arbitrarily. We show that every black-box PRG construction of this form must have stretch s bounded as s /spl les/ 1 /spl middot/ (log/sup O(1)/ n)/m + O(1) = o(l). This holds even if the PRG construction starts from a one-to-one function f : {0,1}/sup n/ /spl rarr/ {0, 1}/sup m/ where m > 5n. This shows that either adaptive queries or sequential computation are necessary for black-box PRG constructions with constant factor stretch (i.e. s = /spl Omega/(l)) from one-way functions, even if the functions are one-to-one. On the positive side we show that if there is a one-way function f : {0, 1}/sup n/ /spl rarr/ {0, 1}/sup m/ that is regular (i.e. the number of preimages of f(x) depends on |x| but not on x) and computable by polynomial-size constant depth circuits then there is a PRG : {0, 1}/sup l/ /spl rarr/ {0, 1}/sup l + 1/ computable by polynomial-size constant depth circuits. This complements our negative result above because one-to-one functions are regular. We also study constructions of average-case hard functions starting from worst-case hard ones, i.e. hardness amplifications. We show that if there is an oracle procedure Ampf in the polynomial time hierarchy (PH) such that Ampf is average-case hard for every worst-case hard f, then there is an average-case hard function in PH unconditionally. Bogdanov and Trevisan (FOGS '03) and Viola (CCC'03) show related. but incomparable negative results.

We exhibit an explicitly computable 'pseudorandom' generator stretching l bits into m(l) = l/sup /spl Omega/(log l)/ bits that look random to constant-depth circuits of size m(l) with log m(l) arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same stretch but only fools circuits of depth 2 with one arbitrary symmetric gate at the top. Our generator fools a strictly richer class of circuits than Nisan's generator for constant depth circuits (Combinatorica '91) (but Nisan's generator has a much bigger stretch). In particular, we conclude that every function computable by uniform poly(n)-size probabilistic constant depth circuits with O(log n) arbitrary symmetric gates is in TIME (2/sup no(1)/) This seems to be the richest probabilistic circuit class known to admit a subexponential derandomization. Our generator is obtained by constructing an explicit function f : {0, 1}/sup n/ /spl rarr/ {0, 1} that is very hard on aver-age for constant-depth circuits of size n/sup /spl epsi//spl middot/log n/ with /spl epsi/log/sup 2/ n it arbitrary symmetric gates, and plugging it into the Nisan-Wigderson pseudorandom generator construction (FOCS '88). The proof of the average-case hardness of this function is a modification of arguments by Razborov and Wigderson (IPL '93), and Hansen and Miltersen (MFCS '04), and combines Hdstad's switching lemma (STOC '86) with a multiparty communication complexity lower bound by Babai, Nisan and Szegedy (STOC '89).

We revisit the problem of hardness amplification in NP, as recently studied by O'Donnell (STOC '02). We prove that if NP has a balanced function f such that any circuit of size s(n) fails to compute f on a 1/poly(n) fraction of inputs, then NP has a function f′ such that any circuit of size s′(n)=s(√n)Ω(1) fails to compute f′ on a 1/2 - 1/s′(n) fraction of inputs. In particular, 1. If s(n)=nω(1), we amplify to hardness 1/2-1/nω(1). 2. If s(n)=2nω(1), we amplify to hardness 1/2-1/2nΩ(1). 3. If s(n)=2(n), we amplify to hardness 1/2-1/2 Ω(sqrtn).These improve the results of O'Donnell, which only amplified to 1/2-1/√n. O'Donnell also proved that no construction of a certain general form could amplify beyond 1/2-1/n. We bypass this barrier by using both derandomization and nondeterminism in the construction of f′.We also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that f is balanced are necessary for "black-box" hardness amplification procedures (such as ours).

We study the complexity of building pseudorandom generators (PRGs) with logarithmic seed length from hard functions. We show that, starting from a function f:{0,1}/sup l//spl rarr/{0,1} that is mildly hard on average, i.e. every circuit of size 2/sup /spl Omega/(l)/ fails to compute f on at least a 1/poly(l) fraction of inputs, we can build a PRG: {0,1}/sup O(logn)//spl rarr/{0,1}/sup n/ computable in ATIME(O(1), logn)=alternating time O(logn) with O(1) alternations. Such a PRG implies BP/spl middot/AC/sub 0/=AC/sub 0/ under DLOGTIME-uniformity. On the negative side, we prove a tight lower bound on black-box PRG constructions that are based on worst-case hard functions. We also prove a tight lower bound on black-box worst-case hardness amplification, which is the problem of producing an average-case hard function starting from a worst-case hard one. These lower bounds are obtained by showing that constant depth circuits cannot compute extractors and list-decodable codes.