We prove a lower bound on the communication complexity of computing the$n$-fold xor of an arbitrary function$f$, in terms of the communication complexity and rank of$f$. We prove that$D(f^{\oplus n}) \geq n\cdot(\frac{\Omega(D(f))}{\log \mathrm{r}\mathrm{k}(t)}-\log \text{rk}(f))$, where here$D(f), D(f^{\oplus n})$represent the deterministic communication complexity, and$\text{rk}(f)$is the rank of$f$. Our methods involve a new way to use information theory to reason about deterministic communication complexity.

We define the marginal information of a communication protocol, and use it to prove XOR lemmas for communication complexity. We show that if every C-bit protocol has bounded advantage for computing a Boolean function f, then every Ω(C √n)-bit protocol has advantage exp(−Ω(n)) for computing the n-fold xor f⊕ n. We prove exponentially small bounds in the average case setting, and near optimal bounds for product distributions and for bounded-round protocols.

We prove anticoncentration bounds for the inner product of two independent random vectors and use these bounds to prove lower bounds in communication complexity. We show that if $A,B$ are subsets of the cube $\{\pm 1\}^n$ with $|A| \cdot |B| \geq 2^{1.01 n}$, and $X \in A$ and $Y \in B$ are sampled independently and uniformly, then the inner product $\langle{X},{Y}\rangle$ takes on any fixed value with probability at most $O(1/\sqrt{n})$. In fact, we prove the following stronger “smoothness" statement: $ \max_{k } \big| \Pr[\langle{X},{Y}\rangle = k] - \Pr[\langle{X},{Y}\rangle = k+4]\big| \leq O(1/n).$ We use these results to prove that the exact gap-hamming problem requires linear communication, resolving an open problem in communication complexity. We also conclude anticoncentration for structured distributions with low entropy. If $x \in \mathbb{Z}^n$ has no zero coordinates, and $B \subseteq \{\pm 1\}^n$ corresponds to a subspace of $\mathbb{F}_2^n$ of dimension $0.51n$, then $\max_k \Pr[\langle{x},{Y}\rangle = k] \leq O(\sqrt{\ln (n)/n})$.

If $k

There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets S_1,...,S_k subset [n] is balancing if for every subset X subset {1,2,...,n} of size n/2, there is an i in [k] so that |S_i cap X| = |S_i|/2. We extend and simplify the framework developed by Hegedűs for proving lower bounds on the size of balancing set families. We prove that if n=2p for a prime p, then k >= p. For arbitrary values of n, we show that k >= n/2 - o(n). We then exploit the connection between balancing families and depth-2 threshold circuits. This connection helps resolve a question raised by Kulikov and Podolskii on the fan-in of depth-2 majority circuits computing the majority function on n bits. We show that any depth-2 threshold circuit that computes the majority on n bits has at least one gate with fan-in at least n/2 - o(n). We also prove a sharp lower bound on the fan-in of depth-2 threshold circuits computing a specific weighted threshold function.

We study a direct-sum question for read-once branching programs. If M(f) denotes the minimum average memory required to compute a function f(x_1,x_2, ..., x_n) how much memory is required to compute f on k independent inputs that arrive in parallel? We show that when the inputs are sampled independently from some domain X and M(f) = Omega(n), then computing the value of f on k streams requires average memory at least Omega(k * M(f)/n). Our results are obtained by defining new ways to measure the information complexity of read-once branching programs. We define two such measures: the transitional and cumulative information content. We prove that any read-once branching program with transitional information content I can be simulated using average memory O(n(I+1)). On the other hand, if every read-once branching program with cumulative information content I can be simulated with average memory O(I+1), then computing f on k inputs requires average memory at least Omega(k * (M(f)-1)).

We consider boolean circuits in which every gate may compute an arbitrary boolean function of k other gates, for a parameter k. We give an explicit function $f:{0,1}^n -> {0,1} that requires at least Omega(log^2(n)) non-input gates when k = 2n/3. When the circuit is restricted to being layered and depth 2, we prove a lower bound of n^(Omega(1)) on the number of non-input gates. When the circuit is a formula with gates of fan-in k, we give a lower bound Omega(n^2/k*log(n)) on the total number of gates. Our model is connected to some well known approaches to proving lower bounds in complexity theory. Optimal lower bounds for the Number-On-Forehead model in communication complexity, or for bounded depth circuits in AC_0, or extractors for varieties over small fields would imply strong lower bounds in our model. On the other hand, new lower bounds for our model would prove new time-space tradeoffs for branching programs and impossibility results for (fan-in 2) circuits with linear size and logarithmic depth. In particular, our lower bound gives a different proof for a known time-space tradeoff for oblivious branching programs.

We show that the deterministic number-on-forehead communication complexity of set disjointness for k parties on a universe of size n is Omega(n/4^k). This gives the first lower bound that is linear in n, nearly matching Grolmusz's upper bound of O(log^2(n) + k^2n/2^k). We also simplify the proof of Sherstov's Omega(sqrt(n)/(k2^k)) lower bound for the randomized communication complexity of set disjointness.

We give new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is either 0 or 2, except for the first layer. For every width $d$ and length $n$, our pseudorandom generator uses a seed of length $O((\log d + \log\log n + \log(1/\epsilon))\log n)$ to produce $n$ bits that cannot be distinguished from a uniformly random string by any regular width $d$ length $n$ read-once branching program, except with probability $\epsilon$. We also give a result for general read-once branching programs, in the case that there are no vertices that are reached with small probability. We show that if a (possibly nonregular) branching program of length $n$ and width $d$ has the property that every vertex in the program is traversed with probability at least $\gamma$ on a uniformly random input, then the error of the generator above is at most $2 \epsilon/\gamma^2$. Finally, we show that the set of all binary strings with less than $d$ nonzero entries forms a hitting set for regular width $d$ branching programs.

We show how to efficiently simulate the sending of a single message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver. This is a generalization and strengthening of the Slepian-Wolf theorem, which shows how to carry out such a simulation with low amortized communication in the case that M is a deterministic function of X. A caveat is that our simulation is interactive. As a consequence, we prove that the internal information cost (namely the information revealed to the parties) involved in computing any relation or function using a two party interactive protocol is exactly equal to the amortized communication complexity of computing independent copies of the same relation or function. We also show that the only way to prove a strong direct sum theorem for randomized communication complexity is by solving a particular variant of the pointer jumping problem that we define. This paper implies that a strong direct sum theorem for communication complexity holds if and only if efficient compression of communication protocols is possible. In particular, together with our result, a recent result of Ganor, Kol, and Raz implies that the strongest version of direct sum for randomized communication complexity is false.

We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4 - ϵ) fraction of all symbols transmitted by the parties are corrupted adversarially, at a cost of increasing the communication in the protocol by a multiplicative factor that depends only on ϵ, using an alphabet whose size depends only on ϵ. This improves on an earlier result of Schulman, who showed how to recover when the fraction of errors is bounded by 1/240. We also show how to simulate an arbitrary protocol with a protocol using the binary alphabet, a constant factor increase in communication, and tolerating a 1/8 - ϵ fraction of errors.

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(μ, f, C) denote the maximum success probability of a 2-party communication protocol for computing the boolean function f(x, y) with C bits of communication, when the inputs (x, y) are drawn from the distribution μ. Let μnbe the product distribution on n inputs and fndenote the function that computes n copies of f on these inputs. We prove that if T log3/2T ≪ (C - 1)√n and suc(μ, f, C)n, fn, T) ≤ exp(-Ω(n)). When μ is a product distribution, we prove a nearly optimal result: as long as T log2T ≪ Cn, we must have suc(μn, fn, T) ≤ exp(-Ω(n)).

We describe new ways to simulate two-party communication protocols to get protocols with potentially less communication. We show that every communication protocol that communicates $C$ bits and reveals $I$ bits of information about the inputs to the participating parties can be simulated by a new protocol involving at most $\tilde{O}(\sqrt{CI})$ bits of communication. If the protocol reveals $I$ bits of information about the inputs to an observer that watches the communication in the protocol, we show how to carry out the simulation with $\tilde{O}(I)$ bits of communication. These results lead to a direct sum theorem for randomized communication complexity. Ignoring polylogarithmic factors, we show that for worst-case computation, computing $n$ copies of a function requires $\sqrt{n}$ times the communication required for computing one copy of the function. For average case complexity, given any distribution $\mu$ on inputs, computing $n$ copies of the function on $n$ inputs sampled independently according to $\mu$ requires $\sqrt{n}$ times the communication for computing one copy. If $\mu$ is a product distribution, computing $n$ copies on $n$ independent inputs sampled according to $\mu$ requires $n$ times the communication required for computing the function. We also study the complexity of computing the sum (or parity) of $n$ evaluations of $f$, and obtain results analogous to those above. Our results give the first compression schemes for general randomized protocols and the first direct sum results in the general setting of randomized and distributional communication complexity, without requiring bound on the number of rounds in the protocol or that the distribution of inputs is independent.

We show how to efficiently convert any boolean formula F into a boolean formula E that is resilient to short-circuit errors (as introduced by Kleitman et al. [KLM94]). A gate has a short-circuit error when the value it computes is replaced by the value of one of its inputs. We guarantee that E computes the same function as F, as long as at most (1/10 - ε) of the gates on each path from the output to an input have been corrupted in E. The corruptions may be chosen adversarially, and may depend on the formula E and even on the input. We obtain our result by extending the Karchmer-Wigderson connection between formulas and communication protocols to the setting of adversarial error. This enables us to obtain error-resilient formulas from error-resilient communication protocols.

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call restriction access. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On one extreme, full restrictions (assigning all variables) correspond to evaluating the device on a complete input, yielding the result of the computation on that input, which is the same as standard black-box access. On the other extreme, empty restrictions (assigning no variables) yield a full description of the original device. We explore the grey-scale of possibilities in the middle.

We show how to efficiently simulate the sending of a message to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver who has some information about the message. This is a generalization and strengthening of the Slepian Wolf theorem, which shows how to carry out such a simulation with low amortized communication in the case that the message is a deterministic function of an input. A caveat is that our simulation is interactive. As a consequence, we prove that the internal information cost(namely the information revealed to the parties) involved in computing any relation or function using a two party interactive protocol is exactly equal to the amortized communication complexity of computing independent copies of the same relation or function. We also show that the only way to prove a strong direct sum theorem for randomized communication complexity is by solving a particular variant of the pointer jumping problem that we define. Our work implies that a strong direct sum theorem for communication complexity holds if and only if efficient compression of communication protocols is possible.

We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4-ε) fraction of all symbols transmitted by the parties are corrupted adversarially, at a cost of increasing the communication in the protocol by a constant factor (the constant depends on epsilon). This encoding uses a constant sized alphabet. This improves on an earlier result of Schulman, who showed how to recover when the fraction of errors is bounded by 1/240. We also show how to simulate an arbitrary protocol with a protocol using the binary alphabet, a constant factor increase in communication and tolerating a (1/8-ε) fraction of errors.

A two-player game is played by cooperating players who are not allowed to communicate. A referee asks the players questions sampled from some known distribution and decides whether they win or not based on a known predicate of the questions and the players' answers. The parallel repetition of the game is the game in which the referee samples n independent pairs of questions and sends the corresponding questions to the players simultaneously. If the players cannot win the original game with probability better than $(1-\epsilon)$, what's the best they can do in the repeated game? We improve earlier results of [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803] and [T. Holenstein, Theory Comput., 5 (2009), pp. 141–172], who showed that the players cannot win all copies in the repeated game with probability better than $(1-\epsilon/2)^{\Omega(n\epsilon^2/c)}$ (here c is the length of the answers in the game), in the following ways: (i) We show that the probability of winning all copies is $(1-\epsilon/2)^{\Omega(\epsilon n)}$ as long as the game is a “projection game,” the type of game most commonly used in hardness of approximation results. (ii) We prove a concentration bound for parallel repetition (of general games) showing that for any constant $0<\delta <\epsilon$, the probability that the players win a $(1-\epsilon+\delta)$ fraction of the games in the parallel repetition is at most $\exp\left(-\Omega_{\epsilon}(\delta^3 n/c)\right)$ (here the constant may depend on $\epsilon$); our result has applications to testing Bell inequalities, since it implies that the parallel repetition of the CHSH game can be used to get an experiment that has a very large classical versus quantum gap. Our first bound is independent of the answer length and has a better dependence on $\epsilon$. By the recent work of Raz [Proceedings of the $49$th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 369–373], this bound is tight. Our bound gives a generic way to improve the soundness of a probabilistically checkable proof (PCP), in a way that is independent of the answer length of the PCP. Using it, for every k, one can convert any q query PCP with answer length c, size $sc$, and soundness $(1-\epsilon)$ into a two-query PCP with answer length $ck$, size $O(ck (2s)^k)$, and soundness $(1-\epsilon/2q)^{\Omega(\epsilon k/q)}$. Another consequence of our bound is that the unique games conjecture of Khot [Proceedings of the $34$th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] can now be shown to be equivalent to the following a priori weaker conjecture: There is an unbounded increasing function $f:\mathbb{R}^+\rightarrow \mathbb{R}^+$ such that for every $\epsilon> 0$, there exists an alphabet size $M(\epsilon)$ for which it is NP-hard to distinguish a unique game with alphabet size M in which a $(1-\epsilon^2)$ fraction of the constraints can be satisfied from one in which a $(1-\epsilon f(1/\epsilon))$ fraction of the constraints can be satisfied.

We give new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is either 0 or 2. For every width d and length n, our pseudorandom generator uses a seed of length O((log d + log log n + log(1/ϵ)) log n) to produce n bits that cannot be distinguished from a uniformly random string by any regular width d length n read-once branching program, except with probability ϵ. We also give a result for general read-once branching programs, in the case that there are no vertices that are reached with small probability. We show that if a (possibly non-regular) branching program of length n and width d has the property that every vertex in the program is traversed with probability at least γ on a uniformly random input, then the error of the generator above is at most 2ϵ/γ2.

We describe new ways to simulate 2-party communication protocols to get protocols with potentially smaller communication. We show that every communication protocol that communicates C bits and reveals I bits of information about the inputs to the participating parties can be simulated by a new protocol involving at most ~O(√CI) bits of communication. If the protocol reveals I bits of information about the inputs to an observer that watches the communication in the protocol, we show how to carry out the simulation with ~O(I) bits of communication.

We give polynomial time computable extractors for low-weight affine sources. A distribution is affine if it samples a random points from some unknown low dimensional subspace of F2n. A distribution is low weight affine if the corresponding linear space has a basis of low-weight vectors. Low-weight affine sources are thus a generalization of the well studied models of bit-fixing sources (which are just weight 1 affine sources). For universal constants c,isin, our extractors can extract almost all the entropy from weight kisinaffine sources of dimension k, as long as k > logcn, with error 2-kOmega(1)In particular, our results give new extractors for low entropy bit-fixing sources, with exponentially small error, a parameter that is important for the application of these extractors to cryptography. Our techniques involve constructing new condensers for affine somewhere random sources.

We show how to efficiently extract truly random bits from two independent sources of linear min-entropy, under a computational assumption. The assumption we rely on is the existence of an efficiently computable permutation f1, such that for any source X ¿ {0, 1}nwith linear min-entropy, any circuit of size poly(n) cannot invert f(X) with non-negligible probability. Under the stronger assumption that f(X) cannot be inverted even by circuits of size poly(nlog n) with nonnegligible probability, we design a lossless computational network extractor protocol. Namely, we design a protocol for a set of players, each with access to an independent source of linear min-entropy, with the guarantee that at the end of the protocol, each honest player is left with bits that are computationally indistinguishable from being uniform and private. Our protocol succeeds as long as there are at least two honest players. Our results imply that if such one-way permutations exist, and enhanced trapdoor permutations exist, then secure multiparty computation with imperfect randomness is possible for any number of players, as long as at least two of them are honest. We also construct a network extractor protocol for the case where each source has only polynomially-small min-entropy (n¿for some constant ¿ > 0). For this we need at least a constant u(¿) (which depends on ¿) number of honest players, and we need that the one-way permutation is hard to invert even on polynomially small min-entropy sources.

We consider the problem of randomness extraction from independent sources. We construct an extractor that can extract from a constant number of independent sources of length n, each of which have min-entropy $n^\gamma$, for an arbitrarily small constant $\gamma>0$. Our extractor is obtained by composing seeded extractors in simple ways. We introduce a new technique to condense independent somewhere-random sources which looks like a useful way to manipulate independent sources. Our techniques are different from those used in recent work [B. Barak, R. Impagliazzo, and A. Wigderson, SIAM J. Comput., 36 (2006), pp. 1095–1118; B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson, Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 1–10; R. Raz, Extractors with weak random seeds, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 11–20; J. Bourgain, Int. J. Number Theory, 1 (2005), pp. 1–32] for this problem in the sense that they do not rely on any results from arithmetic combinatorics. Using an extractor of Bourgain's [Int. J. Number Theory, 1 (2005), pp. 1–32] as a black box, we obtain a new extractor for two independent block sources with few blocks, even when the min-entropy is as small as $\operatorname{polylog}(n)$. We also show how to modify the 2 source disperser for linear min-entropy of Barak et al. [Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 1–10] and the three source extractor of Raz [Extractors with weak random seeds, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 11–20] to get dispersers/extractors with exponentially small error and linear output length where previously both were constant.

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically,denoting by val(G) the value of a two-prover unique game G, andby sdpval(G) the value of a natural semidefinite program to approximate val(G), we prove that for every l epsi N, if sdpval(G) ges 1-delta, then val(Gl) ges 1-radicsldelta. Here, Gldenotes the l-fold parallel repetition of G, and s=O(log(k/delta)), where k denotes the alphabet size of the game. For the special case where G is an XOR game (i.e., k=2), we obtain the same bound but with s as an absolute constant. Our bounds on s are optimal up to a factor of O(log(1/delta)). For games with a significant gap between the quantities val(G) and sdpval(G), our result implies that val(Gl) may be much larger than val(G)l, giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz (FOCS'08) has shown such an example using the max-cut game on oddcycles. Our results are based on a generalization of his techniques.

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

What is the least surface area of a shape that tiles Ropfdunder translations by Zopfd? Any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely Omega(radicd). Our main result is a construction with surface area O(radicd), matching the lower bound up to a constant factor of 2radic2pi/eap3. The best previous tile known was only slightly better than the cube, having surface area on the order of d. We generalize this to give a construction that tiles Ropfdby translations of any full rank discrete lattice Lambda with surface area 2piparV-1parfb, where V is the matrix of basis vectors of Lambda, and par.parfbdenotes the Frobenius norm. We show that our bounds are optimal within constant factors for rectangular lattices. Our proof is via a random tessellation process, following recent ideas of Raz in the discrete setting. Our construction gives an almost optimal noise-resistant rounding scheme to round points in Ropfdto rectangular lattice points.

The main result of this paper is an explicit disperser for two independent sources on n bits, each of entropy k=no(1). Put differently, setting N=2n and K=2k, we construct explicit N x N Boolean matrices for which no K x K submatrix is monochromatic. Viewed as adjacency matrices of bipartite graphs, this gives an explicit construction of K-Ramsey bipartite graphs of size N.This greatly improves the previous bound of k=o(n) of Barak, Kindler, Shaltiel, Sudakov and Wigderson [4]. It also significantly improves the 25-year record of k = Õ (√n) on the special case of Ramsey graphs, due to Frankl and Wilson [9].The construction uses (besides "classical" extractor ideas) almost all of the machinery developed in the last couple of years for extraction from independent sources, including:

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.

We consider the problem of randomness extraction from independent sources. We construct an extractor that can extract from a constant number of independent sources of length n, each of which have min-entropy nγ for an arbitrarily small constant γ > 0. Our extractor is obtained by composing seeded extractors in simple ways. We introduce a new technique to condense independent somewhere-random sources which looks like a useful way to manipulate independent sources. Our techniques are different from those used in recent work [1, 2, 16, 5] for this problem in the sense that they do not rely on any results from additive number theory.Using Bourgain's extractor [5] as a black box, we obtain a new extractor for 2 independent block-sources with few blocks, even when the min-entropy is as small as polylog(n). We also show how to modify the 2 source disperser for linear min-entropy of Barak et al. [2] and the 3 source extractor of Raz [16] to get dispersers/extractors with exponentially small error and linear output length where previously both were constant.In terms of Ramsey Hypergraphs, for every constant 1> γ >0 our construction gives a family of explicit O(1/γ)-uniform hypergraphs on N vertices that avoid cliques and independent sets of size 2(log N)γ.