A group of $n$ users want to run a distributed protocol $π$ over a network where communication occurs via private point-to-point channels. Unfortunately, an adversary, who knows $π$, is able to maliciously flip bits on the channels. Can we efficiently simulate $π$ in the presence of such an adversary? We show that this is possible, even when $L$, the number of bits sent in $π$, and $T$, the number of bits flipped by the adversary are not known in advance. In particular, we show how to create a robust version of $π$ that 1) fails with probability at most $δ$, for any $δ>0$; and 2) sends $\tilde{O}(L + T)$ bits, where the $\tilde{O}$ notation hides a $\log (nL/ δ)$ term multiplying $L$. Additionally, we show how to improve this result when the average message size $α$ is not constant. In particular, we give an algorithm that sends $O( L (1 + (1/α) \log (n L/δ) + T)$ bits. This algorithm is adaptive in that it does not require a priori knowledge of $α$. We note that if $α$ is $Ω\left( \log (n L/δ) \right)$, then this improved algorithm sends only $O(L+T)$ bits, and is therefore within a constant factor of optimal.

Let $\mathcal{L}$ be a language that can be decided in linear space and let $\epsilon \gt 0$ be any constant. Let $\mathcal{A}$ be the exponential hardness assumption that for every n, membership in $\mathcal{L}$ for inputs of length n cannot be decided by circuits of size smaller than $2^{\epsilon n}$. We prove that for every function $f:\{0,1\}^{*} \rightarrow\{0,1\}$, computable by a randomized logspace algorithm R, there exists a deterministic logspace algorithm D (attempting to compute f), such that on every input x of length n, the algorithm D outputs one of the following:1)The correct value $f(x)$.2)The string: “I am unable to compute $f(x)$ because the hardness assumption $\mathcal{A}$ is false”, followed by a (provenly correct) circuit of size smaller than $2^{\epsilon n^{\prime}}$ for membership in $\mathcal{L}$ for inputs of length $n^{\prime}$, for some $n^{\prime}=\Theta(\log n)$; that is, a circuit that refutes $\mathcal{A}$. Moreover, D is explicitly constructed, given R.We note that previous works on the hardness-versus-randomness paradigm give derandomized algorithms that rely blindly on the hardness assumption. If the hardness assumption is false, the algorithms may output incorrect values, and thus a user cannot trust that an output given by the algorithm is correct. Instead, our algorithm D verifies the computation so that it never outputs an incorrect value. Thus, if D outputs a value for $f(x)$, that value is certified to be correct. Moreover, if D does not output a value for $f(x)$, it alerts that the hardness assumption was found to be false, and refutes the assumption.Our next result is a universal derandomizer for BPL (the class of problems solvable by bounded-error randomized logspace algorithms)1: We give a deterministic algorithm U that takes as an input a randomized logspace algorithm R and an input x and simulates the computation of R on x, deteriministically. Under the widely believed assumption $\mathbf{BPL}=\mathbf{L}$, the space used by U is at most $C_{R} \cdot \log n$ (where $C_{R}$ is a constant depending on R). Moreover, for every constant $c \geq 1$, if $\operatorname{BPL} \subseteq \operatorname{SPACE}\left[(\log (n))^{c}\right]$ then the space used by U is at most $C_{R} \cdot(\log (n))^{c}$.Finally, we prove that if optimal hitting sets for ordered branching programs exist then there is a deterministic logspace algorithm that, given a black-box access to an ordered branching program B of size n, estimates the probability that B accepts on a uniformly random input. This extends the result of (Cheng and Hoza CCC 2020), who proved that an optimal hitting set implies a white-box two-sided derandomization.1Our result is stated and proved for promise-BPL, but we ignore this difference in the abstract.

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on n bits requires either Ω(n2) bits of classical memory or an exponential number (in ‍n) of random samples. A line of recent works continued that research direction and showed that for a large collection of classical learning tasks, either super-linear classical memory size or super-polynomially many samples are needed. All these works consider learning algorithms as classical branching programs, which perform classical computation within bounded memory. However, these results do not capture all physical computational models, remarkably, quantum computers and the use of quantum memory. It leaves the possibility that a small piece of quantum memory could significantly reduce the need for classical memory or samples and thus completely change the nature of the classical learning task. Despite the recent research on the necessity of quantum memory for intrinsic quantum learning problems like shadow tomography and purity testing, the role of quantum memory in classical learning tasks remains obscure. In this work, we study classical learning tasks in the presence of quantum memory. We prove that any quantum algorithm with both, classical memory and quantum memory, for parity learning on n bits, requires either Ω(n2) bits of classical memory or Ω(n) bits of quantum memory or an exponential number of samples. In other words, the memory-sample lower bound for parity learning remains qualitatively the same, even if the learning algorithm can use, in addition to the classical memory, a quantum memory of size c n (for some constant c>0). Our result is more general and applies to many other classical learning tasks. Following previous works, we represent by the matrix M: A × X → {−1,1} the following learning task. An unknown x is sampled uniformly at random from a concept class X, and a learning algorithm tries to uncover x by seeing streaming of random samples (ai, bi = M(ai, x)) where for every i, ai∈ A is chosen uniformly at random. Assume that k,ℓ,r are integers such that any submatrix of M of at least 2−k·|A| rows and at least 2−ℓ·|X| columns, has a bias of at most 2−r. We prove that any algorithm with classical and quantum hybrid memory for the learning problem corresponding to M needs either (1) Ω(k · ℓ) bits of classical memory, or (2) Ω(r) qubits of quantum memory, or (3) 2Ω(r) random samples, to achieve a success probability at least 2−O(r). Our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning on these problems. Our results also imply improved security of several existing cryptographical protocols in the bounded-storage model (protocols that are based on parity learning on n bits), proving that security holds even in the presence of a quantum adversary with at most c n2 bits of classical memory and c n bits of quantum memory (for some constant c>0).

We prove that for every 3-player (3-prover) game G with value less than one, whose query distribution has the support S = {(1,0,0), (0,1,0), (0,0,1)} of Hamming weight one vectors, the value of the n-fold parallel repetition G^{⊗n} decays polynomially fast to zero; that is, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For every 3-player game G over binary questions and arbitrary answer lengths, with value less than 1, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Our proof technique is new and requires many new ideas. For example, we make use of the Level-k inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.

We show that quantum algorithms of time $T$ and space $S\ge \log T$ with unitary operations and intermediate measurements can be simulated by quantum algorithms of time $T \cdot \mathrm{poly} (S)$ and space $ {O}(S\cdot \log T)$ with unitary operations and without intermediate measurements. The best results prior to this work required either $Ω(T)$ space (by the deferred measurement principle) or $\mathrm{poly}(2^S)$ time [FR21,GRZ21]. Our result is thus a time-efficient and space-efficient simulation of algorithms with unitary operations and intermediate measurements by algorithms with unitary operations and without intermediate measurements. To prove our result, we study pseudorandom generators for quantum space-bounded algorithms. We show that (an instance of) the INW pseudorandom generator for classical space-bounded algorithms [INW94] also fools quantum space-bounded algorithms. More precisely, we show that for quantum space-bounded algorithms that have access to a read-once tape consisting of random bits, the final state of the algorithm when the random bits are drawn from the uniform distribution is nearly identical to the final state when the random bits are drawn using the INW pseudorandom generator. This result applies to general quantum algorithms which can apply unitary operations, perform intermediate measurements and reset qubits.

We prove that for every 3-player (3-prover) game, with binary questions and answers and value <1, the value of the n-fold parallel repetition of the game decays polynomially fast to 0. That is, for every such game, there exists a constant c>0, such that the value of the n-fold parallel repetition of the game is at most n−c.

We study a new type of separations between quantum and classical communication complexity, separations that are obtained using quantum protocols where all parties are efficient , in the sense that they can be implemented by small quantum circuits, with oracle access to their inputs. Our main result qualitatively matches the strongest known separation between quantum and classical communication complexity Gavinsky (2016) and is obtained using a quantum protocol where all parties are efficient. More precisely, we give an explicit partial Boolean function f over inputs of length N , such that: f can be computed by a simultaneous-message quantum protocol with communication complexity polylog( N ) (where at the beginning of the protocol Alice and Bob also have polylog( N ) entangled EPR pairs). Any classical randomized protocol for f , with any number of rounds, has communication complexity at least \(\tilde{\Omega}\left(N^{1/4}\right)\) . All parties in the quantum protocol of Item (1) (Alice, Bob and the referee) can be implemented by quantum circuits of size polylog( N ) (where Alice and Bob have oracle access to their inputs). Items (1), (2) qualitatively match the strongest known separation between quantum and classical communication complexity, proved by Gavinsky (2016). Item (3) is new. (Our result is incomparable to the one of Gavinsky. While he obtained a quantitatively better lower bound of \(\Omega\left(N^{1/2}\right)\) in the classical case, the referee in his quantum protocol is inefficient). Exponential separations of quantum and classical communication complexity have been studied in numerous previous works, but to the best of our knowledge the efficiency of the parties in the quantum protocol has not been addressed, and in most previous separations the quantum parties seem to be inefficient. The only separations that we know of that have efficient quantum parties are the recent separations that are based on lifting Göös et al. (2017), Chattopadhyay et al. (2019a). However, these separations seem to require quantum protocols with at least two rounds of communication, so they imply a separation of two-way quantum and classical communication complexity, but they do not give the stronger separations of simultaneous-message quantum communication complexity vs. two-way classical communication complexity (or even one-way quantum communication complexity vs. two-way classical communication complexity). Our proof technique is completely new, in the context of communication complexity, and is based on techniques from Raz & Tal (2019). Our function f is based on a lift of the forrelation problem, using xor as a gadget.

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t = t ( n ), where the running time of the prover is poly ( t ) and the running time of the verifier is n · polylog ( t ). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval ( PIR ) scheme. The proof exploits a curious connection between the problem of computation delegation and the model of multi-prover interactive proofs that are sound against no-signaling (cheating) strategies , a model that was studied in the context of multi-prover interactive proofs with provers that share quantum entanglement, and is motivated by the physical principle that information cannot travel faster than light. For any language computable in time t = t ( n ), we construct a multi-prover interactive proof ( MIP ), that is, sound against no-signaling strategies, where the running time of the provers is poly ( t ), the number of provers is polylog ( t ), and the running time of the verifier is n · polylog ( t ). In particular, this shows that the class of languages that have polynomial-time MIP s that are sound against no-signaling strategies, is exactly EXP . Previously, this class was only known to contain PSPACE . To convert our MIP into a 1-round delegation scheme, we use the method suggested by Aiello et al. (ICALP, 2000), which makes use of a PIR scheme. This method lacked a proof of security. We prove that this method is secure assuming the underlying MIP is secure against no-signaling provers.

We present a distribution 𝓓 over inputs in {± 1} 2 N , such that: (1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time O (log N ), that distinguishes between 𝓓 and the uniform distribution with advantage Ω (1/log N ). (2) No Boolean circuit of quasi-polynomial size and constant depth distinguishes between 𝓓 and the uniform distribution with advantage better than polylog(N)/√ N . By well-known reductions, this gives a separation of the classes Promise- BQP and Promise- PH in the black-box model and implies an oracle relative to which BQP is not contained in PH .

In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn x = (x₁,…,x_n) ∈ {0,1}ⁿ from a stream of random linear equations over 𝔽₂ that are correct with probability 1/2+ε and flipped with probability 1/2-ε (0 < ε < 1/2), that any learning algorithm requires either a memory of size Ω(n²/ε) or an exponential number of samples. In fact, we study memory-sample lower bounds for a large class of learning problems, as characterized by [Garg et al., 2018], when the samples are noisy. A matrix M: A × X → {-1,1} corresponds to the following learning problem with error parameter ε: an unknown element x ∈ X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a₁, b₁), (a₂, b₂) …, where for every i, a_i ∈ A is chosen uniformly at random and b_i = M(a_i,x) with probability 1/2+ε and b_i = -M(a_i,x) with probability 1/2-ε (0 < ε < 1/2). Assume that k,𝓁, r are such that any submatrix of M of at least 2^{-k} ⋅ |A| rows and at least 2^{-𝓁} ⋅ |X| columns, has a bias of at most 2^{-r}. We show that any learning algorithm for the learning problem corresponding to M, with error parameter ε, requires either a memory of size at least Ω((k⋅𝓁)/ε), or at least 2^{Ω(r)} samples. The result holds even if the learner has an exponentially small success probability (of 2^{-Ω(r)}). In particular, this shows that for a large class of learning problems, same as those in [Garg et al., 2018], any learning algorithm requires either a memory of size at least Ω(((log|X|)⋅(log|A|))/ε) or an exponential number of noisy samples. Our proof is based on adapting the arguments in [Ran Raz, 2017; Garg et al., 2018] to the noisy case.

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the n-fold GHZ game is at most n^{-Ω(1)}. This was first established by Holmgren and Raz [Holmgren and Raz, 2020]. We present a new proof of this theorem that we believe to be simpler and more direct. Unlike most previous works on parallel repetition, our proof makes no use of information theory, and relies on the use of Fourier analysis. The GHZ game [Greenberger et al., 1989] has played a foundational role in the understanding of quantum information theory, due in part to the fact that quantum strategies can win the GHZ game with probability 1. It is possible that improved parallel repetition bounds may find applications in this setting. Recently, Dinur, Harsha, Venkat, and Yuen [Dinur et al., 2017] highlighted the GHZ game as a simple three-player game, which is in some sense maximally far from the class of multi-player games whose behavior under parallel repetition is well understood. Dinur et al. conjectured that parallel repetition decreases the value of the GHZ game exponentially quickly, and speculated that progress on proving this would shed light on parallel repetition for general multi-player (multi-prover) games.

The Forrelation problem, introduced by Aaronson [A10] and Aaronson and Ambainis [AA15], is a well studied problem in the context of separating quantum and classical models. Variants of this problem were used to give exponential separations between quantum and classical query complexity [A10, AA15]; quantum query complexity and bounded-depth circuits [RT19]; and quantum and classical communication complexity [GRT19]. In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than $\approx 1/\sqrt{N}$, that is, the success probability is larger than $\approx 1/2 + 1/\sqrt{N}$. To achieve separations when the classical protocol has smaller advantage, we study in this work the XOR of $k$ independent copies of the Forrelation function (where $k\ll N$). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level $2k$ is bounded by $α^k$, cannot compute the XOR of $k$ independent copies of the Forrelation function with advantage better than $O\left(\frac{α^k}{N^{k/2}}\right)$. This is a strengthening of a result of [CHLT19], that gave a similar result for $k=1$, using the technique of [RT19]. As an application of our result, we give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol of cost $\mbox{polylog}(N)$ (when players share $\mbox{polylog}(N)$ EPR pairs), however, any classical interactive randomized protocol of cost at most $\tilde{o}(N^{1/4})$, has quasipolynomially small advantage over a random guess. We also give the first example of a partial Boolean function that has a quantum query algorithm of cost $\mbox{polylog}(N)$, and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess.

We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary n× n contraction matrix A, and a parameter T ≤ poly(n) and outputs the entries of A^T, up to (arbitrary) polynomially small additive error. The algorithm applies only unitary operators, without intermediate measurements. We show various implications and applications of this result: First, we use this algorithm to show that the class of quantum logspace algorithms with only quantum memory and with intermediate measurements is equivalent to the class of quantum logspace algorithms with only quantum memory without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms (without classical memory). More generally, we give a quantum algorithm with space O(S + log T) that takes as an input the description of a quantum algorithm with quantum space S and time T, with intermediate measurements (without classical memory), and simulates it unitarily with polynomially small error, without intermediate measurements. Since unitary transformations are reversible (while measurements are irreversible) an interesting aspect of this result is that it shows that any quantum logspace algorithm (without classical memory) can be simulated by a reversible quantum logspace algorithm. This proves a quantum analogue of the result of Lange, McKenzie and Tapp that deterministic logspace is equal to reversible logspace [Lange et al., 2000]. Finally, we use our results to show non-trivial classical simulations of quantum logspace learning algorithms.

We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machines with advice. To the best of our knowledge, this is the first connection between parallel repetition and lower bounds for time complexity and the first major potential implication of a parallel repetition theorem with more than two players. Along the way to proving this result, we define and initiate a study of block rigidity, a weakening of Valiant’s notion of rigidity [Valiant, 1977]. While rigidity was originally defined for matrices, or, equivalently, for (multi-output) linear functions, we extend and study both rigidity and block rigidity for general (multi-output) functions. Using techniques of Paul, Pippenger, Szemerédi and Trotter [Paul et al., 1983], we show that a block-rigid function cannot be computed by multi-tape Turing machines that run in linear (or slightly super-linear) time, even in the non-uniform setting, where the machine gets an arbitrary advice tape. We then describe a class of multiplayer games, such that, a sufficiently strong parallel repetition theorem for that class of games implies an explicit block-rigid function. The games in that class have the following property that may be of independent interest: for every random string for the verifier (which, in particular, determines the vector of queries to the players), there is a unique correct answer for each of the players, and the verifier accepts if and only if all answers are correct. We refer to such games as independent games. The theorem that we need is that parallel repetition reduces the value of games in this class from v to v^Ω(n), where n is the number of repetitions. As another application of block rigidity, we show conditional size-depth tradeoffs for boolean circuits, where the gates compute arbitrary functions over large sets.

We show an exponential gap between communication complexity and external information complexity by analyzing a communication task suggested as a candidate by Braverman [ A Hard-to-Compress Interactive Task?, in Proceedings of the 51th Annual Allerton Conference on Communication, Control, and Computing, IEEE, 2013]. Previously, only a separation of communication complexity and internal information complexity was known. More precisely, we obtain an explicit example of a search problem with external information complexity at most $O(k)$, with respect to any input distribution, and distributional communication complexity at least $2^k$, with respect to some input distribution. In particular, this shows that a communication protocol cannot always be compressed to its external information. By a result of Braverman [ SIAM J. Comput., 44 (2015), pp. 1698--1739], our gap is the largest possible. Moreover, since the upper bound of $O(k)$ on the external information complexity of the problem is obtained with respect to any input distribution, our result implies an exponential gap between communication complexity and information complexity (both internal and external) in the nondistributional setting of Braverman [ SIAM J. Comput., 44 (2015), pp. 1698--1739]. In this setting, no gap was previously known, even for internal information complexity.

In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming setting. In our first result, we show that any algorithm that distinguishes between uniform distribution on $\{0,1\}^n$ and uniform distribution on an $n/2$-dimensional linear subspace of $\{0,1\}^n$ with non-negligible advantage needs $2^{Ω(n)}$ samples or $Ω(n^2)$ memory. Our second result applies to distinguishing outputs of Goldreich's local pseudorandom generator from the uniform distribution on the output domain. Specifically, Goldreich's pseudorandom generator $G$ fixes a predicate $P:\{0,1\}^k \rightarrow \{0,1\}$ and a collection of subsets $S_1, S_2, \ldots, S_m \subseteq [n]$ of size $k$. For any seed $x \in \{0,1\}^n$, it outputs $P(x_{S_1}), P(x_{S_2}), \ldots, P(x_{S_m})$ where $x_{S_i}$ is the projection of $x$ to the coordinates in $S_i$. We prove that whenever $P$ is $t$-resilient (all non-zero Fourier coefficients of $(-1)^P$ are of degree $t$ or higher), then no algorithm, with $

We prove that any two-pass graph streaming algorithm for the s-t reachability problem in n-vertex directed graphs requires near-quadratic space of n2-o(1)bits. As a corollary, we also obtain near-quadratic space lower bounds for several other fundamental problems including maximum bipartite matching and (approximate) shortest path in undirected graphs. Our results collectively imply that a wide range of graph problems admit essentially no non-trivial streaming algorithm even when two passes over the input is allowed. Prior to our work, such impossibility results were only known for single-pass streaming algorithms, and the best two-pass lower bounds only ruled out o(n7/6) space algorithms, leaving open a large gap between (trivial) upper bounds and lower bounds.

We study a new model of space-bounded computation, the random-query model. The model is based on a branching-program over input variables x_1,…,x_n. In each time step, the branching program gets as an input a random index i ∈ {1,…,n}, together with the input variable x_i (rather than querying an input variable of its choice, as in the case of a standard (oblivious) branching program). We motivate the new model in various ways and study time-space tradeoff lower bounds in this model. Our main technical result is a quadratic time-space lower bound for zero-error computations in the random-query model, for XOR, Majority and many other functions. More precisely, a zero-error computation is a computation that stops with high probability and such that conditioning on the event that the computation stopped, the output is correct with probability 1. We prove that for any Boolean function f: {0,1}^n → {0,1}, with sensitivity k, any zero-error computation with time T and space S, satisfies T ⋅ (S+log n) ≥ Ω(n⋅k). We note that the best time-space lower bounds for standard oblivious branching programs are only slightly super linear and improving these bounds is an important long-standing open problem. To prove our results, we study a memory-bounded variant of the coupon-collector problem that seems to us of independent interest and to the best of our knowledge has not been studied before. We consider a zero-error version of the coupon-collector problem. In this problem, the coupon-collector could explicitly choose to stop when he/she is sure with zero-error that all coupons have already been collected. We prove that any zero-error coupon-collector that stops with high probability in time T, and uses space S, satisfies T⋅(S+log n) ≥ Ω(n^2), where n is the number of different coupons.

A line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [Raz, 2016; Kol et al., 2017; Raz, 2017; Moshkovitz and Moshkovitz, 2018; Beame et al., 2018; Garg et al., 2018]. For example, any algorithm for learning parities of size n requires either a memory of size Omega(n^{2}) or an exponential number of samples [Raz, 2016]. All these works modeled the learner as a one-pass branching program, allowing only one pass over the stream of samples. In this work, we prove the first memory-samples lower bounds (with a super-linear lower bound on the memory size and super-polynomial lower bound on the number of samples) when the learner is allowed two passes over the stream of samples. For example, we prove that any two-pass algorithm for learning parities of size n requires either a memory of size Omega(n^{1.5}) or at least 2^{Omega(sqrt{n})} samples. More generally, a matrix M: A x X - > {-1,1} corresponds to the following learning problem: An unknown element x in X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a_1, b_1), (a_2, b_2) ..., where for every i, a_i in A is chosen uniformly at random and b_i = M(a_i,x). Assume that k,l, r are such that any submatrix of M of at least 2^{-k} * |A| rows and at least 2^{-l} * |X| columns, has a bias of at most 2^{-r}. We show that any two-pass learning algorithm for the learning problem corresponding to M requires either a memory of size at least Omega (k * min{k,sqrt{l}}), or at least 2^{Omega(min{k,sqrt{l},r})} samples.

We present a distribution D over inputs in {−1,1}2N, such that: (1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time O(logN), that distinguishes between D and the uniform distribution with advantage Ω(1/logN). (2) No Boolean circuit of quasi-polynomial size and constant depth distinguishes between D and the uniform distribution with advantage better than polylog(N)/√N.

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt et al. (2016) and shows that for some learning problems, a large storage space is crucial. More formally, in the problem of parity learning, an unknown string x ∈ {0,1} n was chosen uniformly at random. A learner tries to learn x from a stream of samples ( a 1 , b 1 ), ( a 2 , b 2 ) …, where each a t is uniformly distributed over {0,1} n and b t is the inner product of a t and x , modulo 2. We show that any algorithm for parity learning that uses less than n 2 /25 bits of memory requires an exponential number of samples. Previously, there was no non-trivial lower bound on the number of samples needed for any learning problem, even if the allowed memory size is O ( n ) (where n is the space needed to store one sample). We also give an application of our result in the field of bounded-storage cryptography. We show an encryption scheme that requires a private key of length n , as well as time complexity of n per encryption/decryption of each bit, and is provably and unconditionally secure as long as the attacker uses less than n 2 /25 memory bits and the scheme is used at most an exponential number of times. Previous works on bounded-storage cryptography assumed that the memory size used by the attacker is at most linear in the time needed for encryption/decryption.

The weak interactive compression conjecture asserts that any two-party communication protocol with communication complexity C and information complexity I can be compressed to a protocol with communication complexity poly(I)polylog(C). We describe a communication problem that is a candidate for refuting that conjecture. Specifically, while we show that the problem can be solved by a protocol with communication complexity C and information complexity I=polylog(C), the problem seems to be hard for protocols with communication complexity poly(I)polylog(C)=polylog(C).

A matrix M: A × X → {−1,1} corresponds to the following learning problem: An unknown element x ∈ X is chosen uniformly at random. A learner tries to learn x from a stream of samples, (a1, b1), (a2, b2) …, where for every i, ai ∈ A is chosen uniformly at random and bi = M(ai,x).

In 1985, Ben-Or and Linial (Advances in Computing Research '89) introduced the collective coin-flipping problem, where n parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party in the course of the protocol as a function of the messages seen so far. They showed that the majority protocol, in which each player sends a random bit and the output is the majority value, tolerates O(sqrt n) adaptive corruptions. They conjectured that this is optimal for such adversaries. We prove that the majority protocol is optimal (up to a poly-logarithmic factor) among all protocols in which each party sends a single, possibly long, message. Previously, such a lower bound was known for protocols in which parties are allowed to send only a single bit (Lichtenstein, Linial, and Saks, Combinatorica '89), or for symmetric protocols (Goldwasser, Kalai, and Park, ICALP '15).

We prove a general memory-samples lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples. Our result is stated in terms of the norm of the matrix that corresponds to the learning problem. Let X, A be two finite sets. A matrix M : A × X → {-1, 1} corresponds to the following learning problem: An unknown element x ∈ X was chosen uniformly at random. A learner tries to learn x from a stream of samples, (a1, b1), (a2, b2) ..., where for every i, ai∈ A is chosen uniformly at random and bi= M(ai, x). Let σmaxbe the largest singular value of M and note that always σmax≤ |A|1/2· |X|1/2. We show that if σmax≤ |A|1/2· |X|1/2-ε, then any learning algorithm for the corresponding learning problem requires either a memory of size at least Ω ((εn)2) or at least 2Ω(εn)samples, where n = log2|X|. As a special case, this gives a new proof for the memory-samples lower bound for parity learning [14].

We define a concept class ℱ to be time-space hard (or memory-samples hard) if any learning algorithm for ℱ requires either a memory of size super-linear in n or a number of samples super-polynomial in n, where n is the length of one sample.

We give an explicit function $h:\{0,1\}^n \to \{0,1\}$ such that every de Morgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. Our technical contributions include a theorem that shows that the “expected shrinkage” result of H\aastad [SIAM J. Comput., 27 (1998), pp. 48--64] actually holds with very high probability (where the restrictions are chosen from a certain distribution that takes into account the structure of the formula), using ideas of Impagliazzo, Meka, and Zuckerman [Proceedings of FOCS, 2012, pp. 111--119].

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager [15] and shows that for some learning problems a large storage space is crucial. More formally, in the problem of parity learning, an unknown string x ϵ {0,1}nwas chosen uniformly at random. A learner tries to learn x from a stream of samples (a1, b1), (a2, b2)..., where each at is uniformly distributed over {0,1}nand bt is the inner product of atand x, modulo 2. We show that any algorithm for parity learning, that uses less than n2/25 bits of memory, requires an exponential number of samples. Previously, there was no non-trivial lower bound on the number of samples needed, for any learning problem, even if the allowed memory size is O(n) (where n is the space needed to store one sample). We also give an application of our result in the field of bounded-storage cryptography. We show an encryption scheme that requires a private key of length n, as well as time complexity of n per encryption/decryption of each bit, and is provenly and unconditionally secure as long as the attacker uses less than n2/25 memory bits and the scheme is used at most an exponential number of times. Previous works on bounded-storage cryptography assumed that the memory size used by the attacker is at most linear in the time needed for encryption/decryption.

It is well known that Linear Programming is P-complete, with a logspace reduction. In this work we ask whether Linear Programming remains P-complete, even if the polyhedron (i.e., the set of linear inequality constraints) is a fixed polyhedron, for each input size, and only the objective function is given as input. More formally, we consider the following problem: maximize c⋅x, subject to Ax ≤ b; x ∈ Rd, where A,b are fixed in advance and only c is given as an input.

We show an exponential gap between communication complexity and information complexity by giving an explicit example of a partial boolean function with information complexity ≤ O ( k ), and distributional communication complexity ≥ 2 k . This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [2015], our gap is the largest possible. By a result of Braverman and Rao [2014], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold, answering a long-standing open problem. Another (conceptual) contribution of our work is the relative discrepancy method, a new rectangle-based method for proving communication complexity lower bounds for boolean functions, powerful enough to separate information complexity and communication complexity.

We study the well-known Label Cover problem under the additional requirement that problem instances have large girth. We show that if the girth is some k , the problem is roughly 2 log 1-ϵ n)/k hard to approximate for all constant ϵ > 0. A similar theorem was claimed by Elkin and Peleg [2000] as part of an attempt to prove hardness for the basic k -spanner problem, but their proof was later found to have a fundamental error. Thus, we give both the first nontrivial lower bound for the problem of Label Cover with large girth as well as the first full proof of strong hardness for the basic k -spanner problem, which is both the simplest problem in graph spanners and one of the few for which super-logarithmic hardness was not known. Assuming NP ⊆ BPTIME (2 polylog(n) , we show (roughly) that for every k ⩾ 3 and every constant ϵ > 0, it is hard to approximate the basic k -spanner problem within a factor better than 2 log 1-ϵ n)/k . This improves over the previous best lower bound of only Ω(log n )/ k from Kortsarz [2001]. Our main technique is subsampling the edges of 2-query probabilistically checkable proofs (PCPs), which allows us to reduce the degree of a PCP to be essentially equal to the soundness desired. This turns out to be enough to basically guarantee large girth.

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model where agent's valuations are unknown to the central planner, and therefore communication is required to determine an efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is n, then r rounds of interaction (with logarithmic bandwidth) suffice to obtain an n1/(r+1)-approximation to the optimal social welfare. In particular, this implies that such markets converge to a stable state (constant approximation) in time logarithmic in the market size. We obtain the first multi-round lower bound for this setup. We show that even if the allowable per-round bandwidth of each agent is nε(r), the approximation ratio of any r-round (randomized) protocol is no better than Ω(n1/5r+1), implying an Ω(log log n) lower bound on the rate of convergence of the market to equilibrium. Our construction and technique may be of interest to round-communication tradeoffs in the more general setting of combinatorial auctions, for which the only known lower bound is for simultaneous (r = 1) protocols [DNO14].

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol for a partial boolean function cannot always be compressed to its internal information. By a result of Braverman [Bra12], our gap is the largest possible. By a result of Braverman and Rao [BR11], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity of boolean functions cannot hold, answering a long standing open problem. Our techniques build on [GKR14], that proved a similar result for relations with very long outputs (double exponentially long in k). In addition to the stronger result, the current work gives a simpler proof, benefiting from the short output length of boolean functions.

In the coin problem, one is given n independent flips of a coin that has bias b > 0 towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply the majority function on the n samples. This simple strategy works as long as b > c(1/sqrt n) for some constant c. However, computing majority is an impossible task for several natural computational models, such as bounded width read once branching programs and AC^0 circuits. Brody and Verbin proved that a length n, width w read once branching program cannot solve the coin problem for b < O(1/(log n)^w). This result was tightened by Steinberger to O(1/(log n)^(w-2)). The coin problem in the model of AC^0 circuits was first studied by Shaltiel and Viola, and later by Aaronson who proved that a depth d size s Boolean circuit cannot solve the coin problem for b < O(1/(log s)^(d+2)). This work has two contributions: 1. We strengthen Steinberger's result and show that any Santha-Vazirani source with bias b < O(1/(log n)^(w-2)) fools length n, width w read once branching programs. In other words, the strong independence assumption in the coin problem is completely redundant in the model of read once branching programs, assuming the bias remains small. That is, the exact same result holds for a much more general class of sources. 2. We tighten Aaronson's result and show that a depth d, size s Boolean circuit cannot solve the coin problem for b < O(1/(log s)^(d-1)). Moreover, our proof technique is different and we believe that it is simpler and more natural.

In 1989, Babai, Nisan and Szegedy gave a construction of a pseudorandom generator for logspace, based on lower bounds for multiparty communication complexity. The seed length of their pseudorandom generator was relatively large, because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for logspace with seed length O(log^2 n) were given by Nisan, and Impagliazzo, Nisan and Wigderson. In this paper, we show how to use the pseudorandom generator construction of Babai, Nisan and Szegedy to obtain a third construction of a pseudorandom generator with seed length O(log^2 n), achieving the same parameters as Nisan, and Impagliazzo, Nisan and Wigderson. We achieve this by concentrating on protocols in a restricted model of multiparty communication complexity that we call the conservative one-way unicast model and is based on the conservative one-way model of Damm, Jukna and Sgall. We observe that bounds in the conservative one-way unicast model (rather than the standard Number On the Forehead model) are sufficient for the pseudorandom generator construction of Babai, Nisan and Szegedy to work. Roughly speaking, in a conservative one-way unicast communication protocol, the players speak in turns, one after the other in a fixed order, and every message is visible only to the next player. Moreover, before the beginning of the protocol, each player only knows the inputs of the players that speak after she does and a certain function of the inputs of the players that speak before she does. We prove a lower bound for the communication complexity of conservative one-way unicast communication protocols that compute a family of functions obtained by compositions of strong extractors. Our final pseudorandom generator construction is related to, but different from the constructions of Nisan, and Impagliazzo, Nisan and Wigderson.

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity ≤ O(k), and distributional communication complexity ≥2k. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [1], our gap is the largest possible. By a result of Braverman and Rao [2], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold.

We construct a 1-round delegation scheme (i.e., argument system) for every language computable in time t = t(n), where the running time of the prover is poly(t) and the running time of the verifier is n · polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. Our construction relies on the existence of a computational sub-exponentially secure private information retrieval (PIR) scheme.

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.

Motivated by the classical problem of privacy amplification, Dodis and Wichs [in Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 601--610] introduced the notion of a nonmalleable extractor, significantly strengthening the notion of a strong extractor. A nonmalleable extractor is a function $\mathsf{nmExt}:\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m$ that takes two inputs---a weak source $W$ and a uniform (independent) seed $S$---and outputs a string $\mathsf{nmExt}(W,S)$ that is nearly uniform given the seed $S$ as well as the value $\mathsf{nmExt}(W,S')$ for any seed $S'\neq S$ that may be determined as an arbitrary function of $S$. The first explicit construction of a nonmalleable extractor was recently provided by Dodis et al. [Privacy Amplification and Non-malleable Extractors via Character Sums, preprint, arXiv:1102.5415 [cs.CR], 2011]. Their extractor works for any weak source with min-entropy rate $1/2+\delta$, where $\delta>0$ is an arbitrary constant and outputs up to a linear number of bits but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols), its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an unconditional construction of a nonmalleable extractor with short seeds. For any integers $n$ and $d$ such that $2.01\cdot\log n\leq d\leq n$, we present an explicit construction of a nonmalleable extractor $\mathsf{nmExt}\colon\{0,1\}^n\times\{0,1\}^d\to\{0,1\}^m$, with $m=\Omega(d)$ and error exponentially small in $m$. The extractor works for any weak source with min-entropy rate $1/2+\delta$, where $\delta>0$ is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of nonmalleability: its output $\mathsf{nmExt}(W,S)$ is nearly uniform given the seed $S$ as well as the values $\mathsf{nmExt}(W,S_1),\dots,\mathsf{nmExt}(W,S_t)$ for several seeds $S_1,\dots,S_t$ that may be determined as an arbitrary function of $S$, as long as $S\notin\{S_1,\dots,S_t\}$. By instantiating the framework of Dodis and Wichs with our nonmalleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate $1/2+\delta$ with asymptotically optimal entropy loss and polylogarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs, whose entropy loss is not asymptotically optimal, and the protocol of Dodis et al., whose communication complexity is linear.

We give an explicit function h: {0, 1}n→ {0, 1} such that every deMorgan formula of size n3-o(1)/r2agrees with h on at most a fraction of 1/2+2-Ω(r)of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013). Our technical contributions include a theorem that shows that the "expected shrinkage" result of Haastad (SIAM J. Comput., 1998) actually holds with very high probability (where the restrictions are chosen from a certain distribution that takes into account the structure of the formula), combining ideas of both Impagliazzo, Meka and Zuckerman (FOCS, 2012) and Komargodski and Raz. In addition, using a bit-fixing extractor in the construction of h allows us to simplify a major part of the analysis of Komargodski and Raz1.

Let C be a (fan-in 2) Boolean circuit of size s and depth d, and let x be an input for C. Assume that a verifier that knows C but doesn't know x can access the low degree extension of x at one random point. Two competing provers try to convince the verifier that C(x)=0 and C(x)=1, respectively, and assume that one of the provers is honest.

We construct a 1-round delegation scheme for every language computable in time t=t(n) and space s=s(n), where the running time of the prover is poly(t) and the running time of the verifier is ~O(n + poly(s)) (where ~O hides polylog(t) factors).

We study the interactive channel capacity of an ε-noisy channel. The interactive channel capacity C(ε) is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel), and the communication complexity of the same problem over the binary symmetric channel with noise rate ε, where the communication complexity tends to infinity.

We give an explicit function h:{0,1}n->{0,1} such that any deMorgan formula of size O(n2.499) agrees with h on at most 1/2 + ε fraction of the inputs, where ε is exponentially small (i.e. ε = 2-nΩ(1)). We also show, using the same technique, that any boolean formula of size O(n1.999) over the complete basis, agrees with h on at most 1/2 + ε fraction of the inputs, where ε is exponentially small (i.e. ε = 2-nΩ(1)). Our construction is based on Andreev's Ω(n2.5-o(1)) formula size lower bound that was proved for the case of exact computation.

We show that any explicit example for a tensor A : [ n ] r → F with tensor-rank ≥ n rċ(1−o(1)) , where r = r ( n ) ≤ log n /log log n is super-constant, implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over F. This shows that strong enough lower bounds for the size of arithmetic formulas of depth 3 imply super-polynomial lower bounds for the size of general arithmetic formulas. One component of our proof is a new approach for homogenization and multilinearization of arithmetic formulas, that gives the following results: We show that for any n -variate homogeneous polynomial f of degree r , if there exists a (fanin-2) formula of size s and depth d for f then there exists a homogeneous formula of size O (( d + r +1 r) ċ s ) for f . In particular, for any r ≤ O (log n ), if there exists a polynomial size formula for f then there exists a polynomial size homogeneous formula for f . This refutes a conjecture of Nisan and Wigderson [1996] and shows that super-polynomial lower bounds for homogeneous formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas. We show that for any n -variate set-multilinear polynomial f of degree r , if there exists a (fanin-2) formula of size s and depth d for f , then there exists a set-multilinear formula of size O (( d + 2) r ċ s ) for f . In particular, for any r ≤ O (log n /log log n ), if there exists a polynomial size formula for f then there exists a polynomial size set-multilinear formula for f . This shows that super-polynomial lower bounds for set-multilinear formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas.

Motivated by the classical problem of privacy amplification, Dodis and Wichs [9] introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor. A non-malleable extractor is a function nmExt : {0, 1}n× {0, 1}d→ {0, 1}mthat takes two inputs: a weak source W and a uniform (independent) seed S, and outputs a string nmExt(W, S) that is nearly uniform given S as well as nmExt(W, S) for any seed S' ≠ S that is determined as an arbitrary function of S. The first explicit construction of a non-malleable extractor was recently provided by Dodis, Li, Wooley and Zuckerman [7]. Their extractor works for any weak source with min-entropy rate 1/2+δ, where δ >; 0 is an arbitrary constant, and outputs up to a linear number of bits, but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols) its efficiency relies on a longstanding conjecture on the distribution of prime numbers. In this paper we present an unconditional construction of a non-malleable extractor with short seeds. For any integers n and d such that 2.01 · log n ≤ d ≤ n, we present an explicit construction of a non-malleable extractor nmExt: {0, 1}n× {0, 1}d→ {0, 1}m, with m = Ω(d), and error exponentially small in m. The extractor works for any weak source with min-entropy rate 1/2 + δ, where δ >; 0 is an arbitrary constant. Moreover, our extractor in fact satisfies an even more general notion of non-malleability: its output nmExt(W, S) is nearly uniform given the seed S as well as the values nmExt(W, S1),..., nmExt(W, St) for several seeds S1,..., St that may be determined as an arbitrary function of S, as long as S ∉ {S1,..., St}. By instantiating the framework of Dodis and Wichs with our non-malleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate 1/2 + δ with asymptotically optimal entropy loss and poly-logarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs whose entropy loss is not asymptotically optimal, and the protocol of Dodis, Li, Wooley and Zuckerman whose communication complexity is linear.

The parallel repetition theorem states that for any Two Prover Game with value at most 1-€ (for €3)Ω(n/s), where s is the length of the answers of the two provers [24], [17]. For Projection Games, the bound on the value of the game repeated n times in parallel was improved to (1 - €2)Ω(n)[23] and this bound was shown to be tight [25]. In this paper we study the case where the underlying distribution, according to which the questions for the two provers are generated, is uniform over the edges of a (bipartite) expander graph. We show that if λ is the (normalized) spectral gap of the underlying graph, the value of the repeated game is at most (1 - €2)Ω(c(λ)·n/s), where c(λ) = poly(λ); and if in addition the game is a projection game, we obtain a bound of (1 - €)Ω(c(λ)·n), where c(λ) = poly(λ), that is, a strong parallel repetition theorem (when λ is constant). This gives a strong parallel repetition theorem for a large class of two prover games.

The Unique Games Conjecture (UGC) is an important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC predicts that such PCP verifiers can have almost-perfect completeness and low-soundness.

This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a written proof for the membership of a given input in an NP language. In this paper, this is achieved by making a constant number of accesses to the proof, obtaining error probability that is exponentially small in the total number of bits that are read. We show that the number of bits that are read in each access to the proof can be made as high as log β n , for any constant β < 1, where n is the length of the proof. The BGLR conjecture asserts the same for any constant β, for β smaller or equal to 1. Our results are in fact stronger, implying that the Gap-Quadratic-Solvability problem with a constant number of variables in each equation is NP-hard. That is, given a system of n quadratic equations over a field $${\mathcal{F}}$$ of size up to $$2^{\log^\beta n}$$ , where each equation depends on a constant number of variables, it is NP-hard to distinguish between the case where there is a common solution to all of the equations and the case where any assignment satisfies at most a $${2 / |\mathcal{F}|}$$ fraction of them. At the same time, our proof presents a direct construction of a low-degree test whose error-probability is exponentially small in the number of bits accessed. Such a result was previously known only relying on recursive applications of the entire PCP theorem.

The parallel repetition theorem states that for any two-prover game with value smaller than 1, parallel repetition reduces the value of the game in an exponential rate. We give a short introduction to the problem of parallel repetition of two-prover games and some of its applications in theoretical computer science, mathematics and physics. We will concentrate mainly on recent results.

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 show that any explicit example for a tensor A:[n]r -> F with tensor-rank ≥ nr ⋅ (1- o(1)), (where r ≤ log n / log log n), implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over F. This shows that strong enough lower bounds for the size of arithmetic formulas of depth 3 imply super-polynomial lower bounds for the size of general arithmetic formulas. One component of our proof is a new approach for homogenization and multilinearization of arithmetic formulas, that gives the following results: We show that for any n-variate homogenous polynomial f of degree r, if there exists a (fanin-2) formula of size s and depth d for f then there exists a homogenous formula of size O ( d+r+1/r ⋅ s) for f. In particular, for any r ≤ log n / log log n, r ≤ log n, if there exists a polynomial size formula for f then there exists a polynomial size homogenous formula for f. This refutes a conjecture of Nisan and Wigderson [10] and shows that super-polynomial lower bounds for homogenous formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas. We show that for any n-variate set-multilinear polynomial f of degree r, if there exists a (fanin-2) formula of size s and depth d for f then there exists a set-multilinear formula of size O ( (d+2)r ⋅ s ) for f. In particular, for any r ≤ log n / log log n, if there exists a polynomial size formula for f then there exists a polynomial size set-multilinear formula for f. This shows that super-polynomial lower bounds for set-multilinear formulas for polynomials of small degree imply super-polynomial lower bounds for general formulas.

We prove an exponential lower bound for the size of constant depth multilinear arithmetic circuits computing either the determinant or the permanent (a circuit is called multilinear, if the polynomial computed by each of its gates is multilinear). We also prove a super-polynomial separation between the size of product-depth d and product-depth d+1 multilinear circuits (where d is constant). That is, there exists a polynomial f such that (1) There exists a multilinear circuit of product-depth d+1 and of polynomial size computing f and (2) Every multilinear circuit of product-depth d computing f has super-polynomial size.

We show that the NP-Complete language 3Sat has a PCPverifier that makes two queries to a proof of almost-linear size and achieves sub-constant probability of error o(1). The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the second query.Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small) constant error and polynomial size.There were also PCP Theorems with sub-constant error andalmost-linear size, but a constant number of queries that is larger than 2.As a corollary, we obtain a host of new results. In particular, our theorem improves many of the hardness of approximation results that are proved using the parallel repetition theorem. A partial list includes the following:(1) 3Sat cannot be efficiently approximated to withina factor of 7/8+o(1), unless P = NP. This holds even under almost-linear reductions. Previously, the best knownNP-hardness factor was 7/8+epsilon for any constant epsilonGt0, under polynomial reductions.(2) 3Lin cannot be efficiently approximated to withina factor of 1/2+o(1), unless P = NP. This holdseven under almost-linear reductions. Previously, the best known NP-hardness factor was 1/2+epsilon for any constant epsilonGt0, under polynomial reductions.(3) A PCP Theorem with amortized query complexity 1 + o(1)and amortized free bit complexity o(1). Previously, the best known amortized query complexity and free bit complexity were 1+epsilon and epsilon, respectively, for any constant epsilon Gt 0.One of the new ideas that we use is a new technique for doing the composition step in the (classical) proof of the PCP Theorem, without increasing the number of queries to the proof. We formalize this as a composition of new objects that we call Locally Decode/Reject Codes (LDRC). The notion of LDRC was implicit in several previous works, and we make it explicit in this work. We believe that the formulation of LDRCs and their construction are of independent interest.

The parallel repetition theorem states that, for any two-prover game with value $1-\epsilon$ (for, say, $\epsilon\leq1/2$), the value of the game repeated in parallel n times is at most $(1-\epsilon^c)^{\Omega(n/s)}$, where s is the answer's length (of the original game) and c is a universal constant [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803]. Several researchers asked whether this bound could be improved to $(1-\epsilon)^{\Omega(n/s)}$; this question is usually referred to as the strong parallel repetition problem. We show that the answer to this question is negative. More precisely, we consider the odd cycle game of size m, a two-prover game with value $1-1/2m$. We show that the value of the odd cycle game repeated in parallel n times is at least $1-(1/m)\cdot O(\sqrt{n})$. This implies that, for large enough n (say, $n\geq\Omega(m^2)$), the value of the odd cycle game repeated in parallel n times is at least $(1-1/4m^2)^{O(n)}$. Thus the following hold. 1. For parallel repetition of general games, the bounds of $(1-\epsilon^c)^{\Omega(n/s)}$ given in [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803; T. Holenstein, in Proceedings of STOC 2002, ACM, New York, 2002, pp. 767–775] are of the right form, up to determining the exact value of the constant $c\geq2$. 2. For parallel repetition of XOR games, unique games, and projection games, the bounds of $(1-\epsilon^2)^{\Omega(n)}$ given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] (for XOR games) and in [A. Rao, in Proceedings of STOC 2008, ACM, New York, 2008, pp. 1–10] (for unique and projection games) are tight. 3. For parallel repetition of the odd cycle game, the bound of $1-(1/m)\cdot\tilde{\Omega}(\sqrt{n})$ given in [U. Feige, G. Kindler, and R. O'Donnell, in Proceedings of CCC 2007, IEEE Computer Society, Washington, DC, 2007, pp. 179–192] is almost tight. A major motivation for the recent interest in the strong parallel repetition problem is that a strong parallel repetition theorem would have implied that the unique game conjecture is equivalent to the NP hardness of distinguishing between instances of Max-Cut that are at least $1-\epsilon^2$ satisfiable from instances that are at most $1-(2/\pi)\cdot\epsilon$ satisfiable. Our results suggest that this cannot be proved just by improving the known bounds on parallel repetition.

A basic fact in linear algebra is that the image of the curve f(x)=(x1,x2,x3,...,xm), say over C, is not contained in any m-1 dimensional affine subspace of Cm. In other words, the image of f is not contained in the image of any polynomial-mapping Γ:Cm-1 → Cm of degree~1 (that is, an affine mapping). Can one give an explicit example for a polynomial curve f:C → Cm, such that, the image of f is not contained in the image of any polynomial-mapping Γ:Cm-1 → Cm of degree 2? In this paper, we show that problems of this type are closely related to proving lower bounds for the size of general arithmetic circuits. For example, any explicit f as above (with the right notion of explicitness implies super-polynomial lower bounds for computing the permanent over~C. More generally, we say that a polynomial-mapping f:Fn → Fm is (s,r)-elusive, if for every polynomial-mapping Γ:Fs → Fm of degree r, Im(f) ⊄ Im(Γ). We show that for many settings of the parameters n,m,s,r, explicit constructions of elusive polynomial-mappings imply strong (up to exponential) lower bounds for general arithmetic circuits. Finally, for every r < log n, we give an explicit example for a polynomial-mapping f:Fn → Fn2, of degree O(r), that is (s,r)-elusive for s = n1+Ω(1/r). We use this to construct for any r, an explicit example for an n-variate polynomial of total-degree O(r), with coefficients in {0,1,}such that, any depth r arithmetic circuit for this polynomial (over any field) is of size ≥ n1+Ω(1/r). In particular, for any constant r, this gives a constant degree polynomial, such that, any depth r arithmetic circuit for this polynomial is of size ≥ n1+Ω(1). Previously, only lower bounds of the type Ω(n • λr (n)), where λr (n) are extremely slowly growing functions (e.g., λ5(n) = log n, and λ7(n) = log* log*n), were known for constant-depth arithmetic circuits for polynomials of constant degree.

We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function (a variant of the Boolean hidden matching problem of Bar-Yossef et al.). Previously, such an exponential separation was known only for a relational problem. The communication problem corresponds to a strong extractor that fails against a small amount of quantum information about its random source. Our proof uses the Fourier coefficients inequality of Kahn, Kalai, and Linial. We also give a number of applications of this separation. In particular, we show that there are privacy amplification schemes that are secure against classical adversaries but not against quantum adversaries; and we give the first example of a key-expansion scheme in the model of bounded-storage cryptography that is secure against classical memory-bounded adversaries but not against quantum ones.

Given (the table of) a function $f : \mathbb{F}^m \rightarrow \mathbb{F}$ over a finite field $\mathbb{F}$, a low degree tester tests its agreement with an m-variate polynomial of total degree at most d over $\mathbb{F}$. The tester is usually given access to an oracle $\mathcal{A}$ providing the supposed restrictions of f to affine subspaces of constant dimension (e.g., lines, planes, etc.). The tester makes very few (probabilistic) queries to f and to $\mathcal{A}$ (say, one query to f and one query to $\mathcal{A}$) and decides whether to accept or reject based on the replies. We wish to minimize two parameters of the tester: its error and its size. The error bounds the probability that the tester accepts although the function is far from a low degree polynomial. The size is the number of bits required to write the oracle replies on all possible tester queries. Low degree testing is a central ingredient in most constructions of probabilistically checkable proofs (PCPs). The error of the low degree tester is related to the error of the PCP, and its size is related to the size of the PCP. We design and analyze new low degree testers that have both subconstant error $o(1)$ and almost-linear size $n^{1+o(1)}$ (where $n = \left|\mathbb{F}\right|^{m}$). Previous constructions of subconstant error testers had polynomial size. These testers enabled the construction of PCPs with subconstant error, but polynomial size. Previous constructions of almost-linear size testers obtained only constant error. These testers were used to construct almost-linear size PCPs with constant error. The testers we present in this work enabled the construction of PCPs with both subconstant error and almost-linear size.

We construct an explicit polynomial $f(x_1,\dots,x_n)$, with coefficients in $\{0,1\}$, such that the size of any syntactically multilinear arithmetic circuit computing f is at least $\Omega(n^{4/3}/\log^2n)$. The lower bound holds over any field.

We construct an explicit polynomial f(x1,..., xn), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Omega{n4/3log2n} The lower bound holds over any field.

We give an exponential separation between one-way quantum and classical communication protocols for twopartial Boolean functions, both of which are variants of the Boolean Hidden Matching Problem of Bar-Yossef et al. Earlier such an exponential separation was known only for a relational version of the Hidden Matching Problem. Our proofs use the Fourier coefficients inequality of Kahn, Kalai, and Linial. We give a number of applications of this separation. In particular, in the bounded-storage model of cryptography we exhibita scheme that is secure against adversaries with a certain amount of classical storage, but insecure against adversaries with a similar (or even much smaller) amount of quantum storage; in the setting of privacy amplification, we show that there are strong extractors that yield a classically secure key, but are insecure against a quantum adversary.

Let Lambda : {0, 1}ntimes {0,1}mrarr {0,1} be a Boolean formula of size d, or more generally, an arithmetic circuit of degree d, known to both Alice and Bob, and let y isin {0,1}mbe an input known only to Alice. Assume that Alice and Bob interacted in the past in a preamble phase (that is, applied a preamble protocol that depends only on the parameters, and not on Lambday). We show that Alice can (non-interactively) commit to y, by a message of size poly(m, log d), and later on prove to Bob any N statements of the form Lambda (x1, y) = z1,..., Lambda(xN,y) = zNby a (computationally sound) non-interactive zero-knowledge proof of size poly(d, log N). (Note the logarithmic dependence on N). We give many applications and motivations for this result. In particular, assuming that Alice and Bob applied in the past the (poly-logarithmic size) preamble protocol: 1. given a CNF formula Psi(w1,..., wm) of size N, Alice can prove the satisfiability of Psi by a (computationally sound) non-interactive zero-knowledge proof of size poly(m). That is, the size of the proof depends only on the size of the witness and not on the size of the formula. 2. Given a language L in the class LOGSNP and an input x isin {0, 1}n, Alice can prove the membership x isin L by a (computationally sound) non-interactive zero-knowledge proof of size polylog n. 3. Alice can commit to a Boolean formula y of size m, by a message of size poly(m), and later on prove to Bob any N statements of the form y(x1) = z1,..., y(xN) = zNby a (computationally sound) non-interactive zero-knowledge proof of size poly(m, log N). Our cryptographic assumptions include the existence of a poly-logarithmic symmetric-private-information-retrieval (SPIR) scheme, as defined in (C. Cachin et. al, 1999), and the existence of commitment schemes, secure against circuits of size exponential in the security parameter

An $(n,k)$‐bit‐fixing source is a distribution X over $\{0,1\}^n$ such that there is a subset of k variables in $X_1,\ldots,X_n$ which are uniformly distributed and independent of each other, and the remaining $n-k$ variables are fixed. A deterministic bit‐fixing source extractor is a function $E:\{0,1\}^n \rightarrow \{0,1\}^m$ which on an arbitrary $(n,k)$‐bit‐fixing source outputs m bits that are statistically close to uniform. Recently, Kamp and Zuckerman [Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 92–101] gave a construction of a deterministic bit‐fixing source extractor that extracts $\Omega(k^2/n)$ bits and requires $k>\sqrt{n}$. In this paper we give constructions of deterministic bit‐fixing source extractors that extract $(1-o(1))k$ bits whenever $k>(\log n)^c$ for some universal constant $c>0$. Thus, our constructions extract almost all the randomness from bit‐fixing sources and work even when k is small. For $k \gg \sqrt{n}$ the extracted bits have statistical distance $2^{-n^{\Omega(1)}}$ from uniform, and for $k \le \sqrt{n}$ the extracted bits have statistical distance $k^{-\Omega(1)}$ from uniform. Our technique gives a general method to transform deterministic bit‐fixing source extractors that extract few bits into extractors which extract almost all the bits.

An (n, k)-affine source over a finite field F is a random variable X = (X/sub 1/, ..., X/sub n/) /spl epsi/ F/sub n/, which is uniformly distributed over an (unknown) k-dimensional affine subspace of F/sub n/. We show how to (deterministically) extract practically all the randomness from affine sources, for any field of size larger than n/sup c/ (where c is a large enough constant). Our main results are as follows: 1. (For arbitrary k): For any n, k and any F of size larger than n/sub 20/, we give an explicit construction for a function D : F/sub n/ /spl rarr/ F/sub k-1/, such that for any (n, k)-affine source X over F, the distribution of D(X) is /spl epsiv/-close to uniform, where /spl epsiv/ is polynomially small in |F|. 2. (For k = 1): For any n and any F of size larger than n/sup c/, we give an explicit construction for a function D : F/sup n/ /spl rarr/ {0,1}/sup (1-/spl sigma/)log//sub 2/|F|, such that for any (n, 1)-affine source X over F, the distribution of D(X) is /spl epsiv/-close to uniform, where /spl epsiv/ is polynomially small in |F|. Here, /spl delta/ > 0 is an arbitrary small constant, and c is a constant depending on /spl delta/.

Our main result is that the membership x /spl epsi/ SAT (for x of length n) can be proved by a logarithmic-size quantum state |/spl Psi/>, together with a polynomial-size classical proof consisting of blocks of length polylog(n) bits each, such that after measuring the state |/spl Psi/> the verifier only needs to read one block of the classical proof. This shows that if a short quantum witness is available then a (classical) PCP with only one query is possible. Our second result is that the class QIP/qpoly contains all languages. That is, for any language L (even non-recursive), the membership x /spl epsi/ L (for x of length n) can be proved by a polynomial-size quantum interactive proof, where the verifier is a polynomial-size quantum circuit with working space initiated with some quantum state |/spl Psi//sub L,n/> (depending only on L and n). Moreover, the interactive proof that we give is of only one round, and the messages communicated are classical. The advice |/spl Psi//sub L,n/> given to the verifier can also be replaced by a classical probabilistic advice, as long as this advice is kept as a secret from the proven Our result can hence be interpreted as: the class IP/rpoly contains all languages. For the proof of the second result, we introduce the quantum low-degree-extension of a string of bits. The main result requires an additional machinery of quantum low-degree-test.

We show how to extract random bits from two or more independent weak random sources in cases where only one source is of linear min-entropy and all other sources are of logarithmic min-entropy. Our main results are as follows:

We give a deterministic polynomial time algorithm for polynomial identity testing in the following two cases: 1. Non commutative arithmetic formulas: the algorithm gets as an input an arithmetic formula in the non-commuting variables x/sub i/,...,x/sub n/ and determines whether or not the output of the formula is identically 0 (as a formal expression). 2. Pure arithmetic circuits: the algorithm gets as an input a pure arithmetic circuit (as defined by N. Nisan and A. Wigderson (1996)) in the variables x/sub i/,...,x/sub n/ and determines whether or not the output of the circuit is identically 0 (as a formal expression). We also give a deterministic polynomial time identity testing algorithm for non commutative algebraic branching programs as defined by N. Nisan (1991). One application is a deterministic polynomial time identity testing for multilinear arithmetic circuits of depth 3. Finally, we observe an exponential lower bound for the size of pure arithmetic circuits for the permanent and for the determinant. (Only lower bounds for the depth of pure circuits were previously known by N. Nisan and A. Wigderson (1996).

We study the power of quantum proofs, or more precisely, the power of quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the linear sub-spaces distance problem. The problem is of geometrical nature: each player gets a linear subspace of R/sup m/ and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 /spl middot/ /spl radic/2) and 0 if the distance is very large (say, larger than 0.9 /spl middot/ /spl radic/2). We show that: 1. The QMA communication complexity of the problem is O(logm). 2. The (classical) MA communication complexity of the problem is /spl Omega/(m/sup /spl epsi//) (for some /spl epsi/ > 0). 3. The (standard) quantum communication complexity of the problem is /spl Omega/(/spl radic/m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity. For the black box model we give several observations. First, we observe that the block sensitivity method, as well as the polynomial method for proving lower bounds for the number of queries, can both be extended to QMA protocols. We use these methods to obtain lower bounds for the QMA black box complexity of functions. In particular, we obtain a tight lower bound of /spl Omega/(N) for the QMA black box complexity of a random function, and a tight lower bound of /spl Omega/(/spl radic/N) for the QMA black box query complexity of NOR(X/sub 1/,..., X/sub n/). In particular, this shows that any attempt to give short quantum proofs for the class of languages Co - NP have to go beyond black box arguments. We also observe that for any Boolean function G(X/sub 1/,..., X/sub n/), if for both G and 7minus;G there are QMA black box protocols that make at most T queries to the black box, then there is a classical deterministic black box protocol for G that makes 0(T/sup 6/) queries to the black box. In particular, this shows that in the black box model QMA /spl cap/ Co - QMA = P. On the positive side, we observe that any (total or partial) Boolean function G(X/sub 1/,..., X/sub n/) has a QMA black box protocol with proofs of length N that makes only 0(/spl radic/N) queries to the black box. Finally, we observe a very simple proof for the exponential separation (for promise problems) between QMA black box complexity and (classical) MA black box complexity (first obtained by Watrous).

An {n, k)-bit-fixing source is a distribution X over {0, 1}/sup n/ such that there is a subset of k variables in X/sub 1/, ..., X/sub n/ which are uniformly distributed and independent of each other, and the remaining n - k variables are fixed. A deterministic bit-fixing source extractor is a function E : {0, l}/sup n/ /spl rarr/ {0, l}/sup m/ which on an arbitrary (n, k)-bit-fixing source outputs m bits that are statistically-close to uniform. Recently, Kamp and Zuckerman (2003) gave a construction of deterministic bit-fixing source extractor that extracts /spl Omega/(k/sup 2//n) bits, and requires k > /spl radic/n. In this paper we give constructions of deterministic bit-fixing source extractors that extract (1 -o(1))k bits whenever k > (log n)/sup c/ for some universal constant c > 0. Thus, our constructions extract almost all the randomness from bit-fixing sources and work even when k is small. For k /spl Gt/ /spl radic/n the extracted bits have statistical distance 2/sup -n/spl Omega/(1)/ from uniform, and for k /spl les/ /spl radic/n the extracted bits have statistical distance k/sup -/spl Omega/(1)/ from uniform. Our technique gives a general method to transform deterministic bit-fixing source extractors that extract few bits into extractors which extract almost all the bits.

An arithmetic circuit or formula is multilinear if the polynomial computed at each of its wires is multilinear. We give an explicit example for a polynomial f(x/sub 1/,..., x/sub n/), with coefficients in {0,1}, such that over any field: (1) f can be computed by a polynomial-size multilinear circuit of depth O(log/sup 2/ n). (2) Any multilinear formula for f is of size n/sup /spl Omega/(log n)/. This gives a super-polynomial gap between multilinear circuit and formula size, and separates multilinear NC/sub 1/ circuits from multilinear NC/sub 2/ circuits.

An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear. We prove that any multi-linear arithmetic formula for the permanent or the determinant of an n x n matrix is of size super-polynomial in n.Previously, super-polynomial lower bounds were not known (for any explicit function) even for the special case of multi-linear formulas of constant depth.

We prove a quasi-polynomial lower bound on the size of bounded-depth Frege proofs of the pigeonhole principle $PHP^{m}_n$ where $m= (1+1/{ípolylog n})n$. This lower bound qualitatively matches the known quasi-polynomial-size bounded-depth Frege proofs for these principles. Our technique, which uses a switching lemma argument like other lower bounds for bounded-depth Frege proofs, is novel in that the tautology to which this switching lemma is applied remains random throughout the argument.

Our main result is a lower bound of $\Omega(m^2 \log m)$ for the size of any arithmetic circuit for the product of two matrices, over the real or complex numbers, as long as the circuit does not use products with field elements of absolute value larger than 1 (where m × m is the size of each matrix). That is, our lower bound is superlinear in the number of inputs and is applied for circuits that use addition gates, product gates, and products with field elements of absolute value up to 1. We also prove size-depth tradeoffs for such circuits: We show that if a circuit, as above, is of depth d, then its size is $\Omega(m^{2+ 1/O(d)})$.

We prove superlinear lower bounds for the number of edges in constant depth circuits with n inputs and up to n outputs. Our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits and constant depth Boolean circuits with arbitrary gates. The bounds apply for several explicit functions and, most importantly, for matrix product. In particular, we obtain the following results: We show that the number of edges in any constant depth arithmetic circuit for matrix product (over any field) is superlinear in m 2 (where m × m is the size of each matrix). That is, the lower bound is superlinear in the number of input variables. Moreover, if the circuit is bilinear, the result applies also for the case in which the circuit gets any product of two linear functions for free. We show that the number of edges in any constant depth arithmetic circuit for the trace of the product of three matrices (over fields with characteristic 0) is superlinear in m 2 . (Note that the trace is a single-output function.) We give explicit examples for n Boolean functions f 1 ,. . .,f n , such that any constant depth Boolean circuit with arbitrary gates for f 1 ,. . .,f n has a superlinear number of edges. The lower bound is also proved for circuits with arbitrary gates over any finite field. The bound applies for matrix product over finite fields as well as for several other explicit functions.

We prove a quasi-polynomial lower bound on the size of bounded-depth Frege proofs of the pigeonhole principle PHP/sub n//sup m/ where m = (1 + 1/polylog n)n. This lower bound qualitatively matches the known quasipolynomial-size bounded-depth Frege proofs for these principles. Our technique, which uses a switching lemma argument like other lower bounds for bounded-depth Frege proofs, is novel in that the tautology to which this switching lemma is applied remains random throughout the argument.

We prove a lower bound of Ω(m2 log m) for the size of any arithmetic circuit for the product of two matrices, over the real or complex numbers, as long as the circuit doesn't use products with field elements of absolute value larger than 1 (where mxm is the size of each matrix). That is, our lower bound is super-linear in the number of inputs and is applied for circuits that use addition gates, product gates and products with field elements of absolute value up to 1. More generally, for any c = c(m) ρ 1, we obtain a lower bound of Ω(m2 log2c m) for the size of any arithmetic circuit for the product of two matrices (over the real or complex numbers), as long as the circuit doesn't use products with field elements of absolute value larger than c. We also prove size-depth tradeoffs for such circuits.

We prove a lower bound of 4.5n - o(n) for the circuit complexity of an explicit Boolean function (that is, a function constructible in deterministic polynomial time), over the basis U_2. That is, we obtain a lower bound of 4.5n - o(n) for the number of {and,or} gates needed to compute a certain Boolean function, over the basis {and,or,not} (where the not gates are not counted). Our proof is based on a new combinatorial property of Boolean functions, called Strongly-Two-Dependence, a notion that may be interesting in its own right. Our lower bound applies to any Strongly-Two-Dependent Boolean function.

We prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length Ω(2^{n^{ε}}), (for some global constant ε > 0$).

We prove a lower bound of 2fl((~)~) onthemonotone size of an explicit function in monotone-Af:P (where n is the number of input variables).This is higher than any previous lower bound on the monotone size of a function.The previous best being a lower bound of about 2 ~('~¼) for Andreev's function, proved in [A1Bo87].Our lower bound is proved by the symmetric version of Razborov's method of approximations.However, we present this method in a new and simpler way: Rather than building approximator functions for all the gates in a circuit, we use a gate elimination argument that is based on a Monotone Switching Lemma.The bound applies for a family of functions, each defined by a construction of a small probability space of c-wise independent random variables.

The interpolation method has been one of the main tools for proving lower bounds for propositional proof systems. Loosely speaking, if one can prove that a particular proof system has the feasible interpolation property, then a generic reduction can (usually) be applied to prove lower bounds for the proof system, sometimes assuming a (usually modest) complexity-theoretic assumption. In this paper, we show that this method cannot be used to obtain lower bounds for Frege systems, or even for TC 0 -Frege systems. More specifically, we show that unless factoring (of Blum integers) is feasible, neither Frege nor TC 0 -Frege has the feasible interpolation property. In order to carry out our argument, we show how to carry out proofs of many elementary axioms/theorems of arithmetic in polynomial-sized TC 0 -Frege. As a corollary, we obtain that TC 0 -Frege, as well as any proof system that polynomially simulates it, is not automatizable (under the assumption that factoring of Blum integers is hard). We also show under the same hardness assumption that the k-provability problem for Frege systems is hard.

An extractor is a function which extracts (almost) truly random bits from a weak random source, using a small number of additional random bits as a catalyst. We present a general method to reduce the error of any extractor. Our method works particularly well in the case that the original extractor extracts up to a constant function of the source min-entropy and achieves a polynomially small error. In that case, we are able to reduce the error to (almost) any /spl epsiv/, using only O(log(1//spl epsiv/)) additional truly random bits (while keeping the other parameters of the original extractor more or less the same). In other cases (e.g. when the original extractor extracts all the min-entropy or achieves only a constant error), our method is not optimal but it is still quite efficient and leads to improved constructions of extractors. Using our method, we are able to improve almost all known extractors in the case where the error required is relatively small (e.g. less than a polynomially small error). In particular, we apply our method to the new extractors of L. Trevisan (1999) and R. Raz et al. (1999) to obtain improved constructions in almost all cases. Specifically, we obtain extractors that work for sources of any min-entropy on strings of length n which (a) extract any 1/n/sup /spl gamma// fraction of the min-entropy using O[log n+log(1//spl epsiv/)] truly random bits (for any /spl gamma/>0), (b) extract any constant fraction of the min-entropy using O[log/sup 2/n+log(1//spl epsiv/)] truly random bits, and (c) extract all the min-entropy using O[log/sup 3/n+log n/spl middot/log(1//spl epsiv/)] truly random bits.

This paper strengthens the law-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture.Namely, we prove that witnesses for membership in any NP language can be verified with a constant nunbcr of accesses, and with an error probability exponentially small in the number of bits accessed, where this number is as high as lagan, for any constant fl < 1. (The BGLR conjecture claims the same for any p 5 1).Our results are in fact stronger, implying the Gap-Quadratic-Solvability problem to be NP-hard even if the equations are restricted to having a constant number of variables.That is, given a system of quadratic-equations over a field 3 (of size up to ZLogD"), where each equation depends on a constant number of variables, it is NP-hard to decide between the case where there is a common solution for all of the equations, and the case where any assignment satisfies no more than a & fraction of them.At the same time, ow proof presents a direct eonstmction of a low-degree-test whose error-probability is expancntially small in the number of hits accessed.Such a result was previously known only relying on recursive applications of the entire PCP theorem.

Communication complexity has become a central completity model.In that model, we count the amount of communication bits needed between two parties in order to solve certain computational problems.We show that for certain communication complezity problems quantum communication protocols are exponentially faster than classical ores.More explicitly, we give an example for a communication complexity relation (0~ promise problem) P such that: 1) The quantum communication complexity of P is O(log m). 2) The classical probabilistic communication complexity of P is Q(m'l'/ logm).(where m is the length of the inputs).This gives an ezponential gap between quantum communication complexity and classical probabilistic communication complexity.Only a quadratic gap was previously known.Our problem P is of geometrical nature, and is a finite precision variation of the following problem: Player I gets as input a unit vector z E R" and two orthogonal subspaces MO, MI c R". Player II gets as input an orthogonal matrixT : R" + R".Their goal is to answer 0 if T(x) E MO and 1 if T(x) E M,, (and any an~luer in any other case).We give an almost tight analysis for the quantum communication complexity and for the classical-probabilistic communication complexity of this problem.

Let M be a logarithmic space Turing machine (or a polynomial width branching program) that uses up to k 2 p log n (read once) random bits. For a fixed input, let P i (S) be the probability (over the random string) that at time i the machine M is in state S, and assume that some weak estimation of the probabilities P i (S) is known or given or can be easily computed. We construct a logarithmic space pseudo-random generator that uses only logarithmic number of truly random bits and outputs a sequence of k bits that looks random to M . This means that a very weak estimation of the state probabilities of M is sufficient for a full derandomization of M and for constructing pseudo-random sequences for M . We have several applications of the main theorem, as stated within. To prove our theorem, we introduce the idea of recycling the state S of the machine M at time i as part of the random string for the same machine at later time. That is, we use the entropy of the random variable S in o...

We give explicit constructions of extractors which work for a source of any min.entropyon strings of length n.The first construction extracts any constant fraction of the min-entropy using O(log* n) additional random bits, The second extracts all the tin-entropy using O(log3 n) additional random bits.Both of these constmcdons use fewer truly random bits than any previous construction which works for all min.entropiesand extracts a constant fraction of the min.entropy.We then improve our second construction and show that we can reduce the entropy loss to 2 log(l/e) +0(l) bits, while still using O(log3 n) truly random bits (where entropy loss is defined as [(source min-entropy) + (# truly random bits used) -(#output bits)], and E is the statistical difference from uniform achieved).This entropy loss is optimal up to a constant additive term.Our extractors are obtained by observing that a weaker notion of "combinatorial design" suffices for the Nisan-Wigderson pseudorandom generator, which underlies the recent extractor of Trevisa We give near-optimal constructions of such "weak designs" which achieve much better parameters than possible with the notion of designs used by Nisan-Wigderson and Trevisan.We also show how to improve our constructions (and Trevisan's construction) when the required statistical difference from uniform distribution E is relatively small.This improvement is obtained by using multilinear error correcting codes over finite fields, rather than the arbitrary error correcting codes used by Trevisan.

We show that a parallel repetition of any two-prover one-round proof system (MIP(2,1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. The dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [U. Feige and O. Verbitsky, Proc.11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 70--76].

The interpolation method has been one of the main tools for proving lower bounds for propositional proof systems. Loosely speaking, if one can prove that a particular proof system has the feasible interpolation property, then a generic reduction can (usually) be applied to prove lower bounds for the proof system, sometimes assuming a (usually modest) complexity-theoretic assumption. In this paper, we show that this method cannot be used to obtain lower bounds for Frege systems, or even for TC/sup 0/-Frege systems. More specifically, we show that unless factoring is feasible, neither Frege nor TC/sup 0/-Frege has the feasible interpolation property. In order to carry out our argument, we show how to carry out proofs of many elementary axioms/theorems of arithmetic in polynomial-size TC/sup 0/-Frege. In particular, we show how to carry out the proof for the Chinese Remainder Theorem, which may be of independent interest. As a corollary, we obtain that TC/sup 0/-Frege as well as any proof system that polynomially simulates it, is not automatizable (under a hardness assumption).

We prove tight lower bounds, of up to n/sup /spl epsiv//, for the monotone depth of functions in monotone-P. As a result we achieve the separation of the following classes. 1. Monotone-NC/spl ne/monotone-P. 2. /spl forall/i/spl ges/1, monotone-NC/sup i//spl ne/monotone-NC/sup i+1/. 3. More generally: For any integer function D(n), up to n/sup /spl epsiv// (for some /spl epsiv/>0), we give an explicit example of a monotone Boolean function, that can be computed by polynomial size monotone Boolean circuits of depth D(n), but that cannot be computed by any (fan-in 2) monotone Boolean circuits of depth less than Const/spl middot/D(n) (for some constant Const). Only a separation of monotone-NC/sup 1/ from monotone-NC/sup 2/ was previously known. Our argument is more general: we define a new class of communication complexity search problems, referred to below as DART games, and we prove a tight lower bound for the communication complexity of every member of-this class. As a result we get lower bounds for the monotone depth of many functions. In particular, we get the following bounds: 1. For st-connectivity, we get a tight lower bound of /spl Omega/(log/sup 2/ n). That is, we get a new proof for Karchmer-Wigderson's theorem, as an immediate corollary of our general result. 2. For the k-clique function, with k/spl les/n/sup /spl epsiv//, we get a tight lower bound of /spl Omega/(k log n). Only a bound of /spl Omega/(k) was previously known.

This paper contains several results regarding the communication complexitymodel and the 2-prover games model, which are based on interaction between the two models:1. 2.The We show how to improve the rate of exponential decrease in the parallel repetition theorem of [Ra] in terms of the communication complexity of the verifier's predicate.We apply the improved parallel repetition theorem of 2-prover games to derive, for the first time, a direct product theorem for communication complexity.second derivation uses a common .qeneralization of the two models, which is independently interesting.We initiate a study of its power by considering the GCD problem, and some variations of it, which exhibit a power gap between the new model and the classical communication complexity model.This gap is partly based on the following upper bounds: Given n-bzt inputs x and y to Alice and Bob respectively, they can achieve the tasks below with very high probability using only O(n/ log n) communication bits:1. Decide if GCD(X, y) = 1.

We introduce a new low-degree--test, one that uses the restriction of low-degree polynomials to planes (i.e., affine sub-spaces of dimension 2), rather than the restriction to lines (i.e., affine sub-spaces of dimension 1). We prove the new test to be of a very small errorprobability (in particular, much smaller than constant). The new test enables us to prove a low-error characterization of NP in terms of PCP. Specifically, our theorem states that, for any given ffl ? 0, membership in any NP language can be verified with O(1) accesses, each reading logarithmic number of bits, and such that the error-probability is 2 \\Gamma log 1\\Gammaffl n . Our results are in fact stronger, as stated below. One application of the new characterization of NP is that approximating SET-COVER to within a logarithmic factors is NP-hard. Previous analysis for low-degree-tests, as well as previous characterizations of NP in terms of PCP, have managed to achieve, with constant number of accesses, error...

Abstract We consider small-weight Cutting Planes (CP*) proofs; that is, Cutting Planes (CP) proofs with coefficients up to Poly(n). We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP* proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution. We also prove the following two theorems: (1) Tree-like CP* proofs cannot polynomially simulate non-tree-like CP* proofs. (2) Tree-like CP* proofs and Bounded-depth-Frege proofs cannot polynomially simulate each other. Our proofs also work for some generalizations of the CP* proof system. In particular, they work for CP* with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference.

We consider small-weight Cutting Planes (CP* ) proofs;Our proofs also work for some generalizations of the C'P* proof system.In particular, they work for CP* with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference.

We show that a parallel repetition of two-prover oneround proof systems (MIP(2, 1)) reduces the probability of error at an exponential rate.This settles a standing open problem, sometimes called 'The Parallel Repetition Conjecture".Previously, no constructive bound was known.The constant we have in the exponent is logarithmic in the total number of possible answers of the two provers.This is significantly better than what was previously known even in the much stmpler case where the questions to the two provers are chosen independently at random.In the most frequently used cases, our constant is just a global constant.

We show the existence of a non-constant gap between the communication complexity of a function and the logarithm of the rank of its input matrix. We consider the following problem: each of two players gets a perfect matching between two n-element sets of vertices. Their goal is to decide whether or not the union of the two matchings forms a Hamiltonian cycle. We prove: (1) The rank of the input matrix over the reals for this problem is 2/sup O(n)/. (2) The non-deterministic communication complexity of the problem is /spl Omega/(n log log n). Our result also supplies a superpolynomial gap between the chromatic number of a graph and the rank of its adjacency matrix. Another conclusion from the second result is an /spl Omega/(n log log n). Lower bound for the graph connectivity problem in the non-deterministic case. We make use of the theory of group representations for the first result. The second result is proved by an information theoretic argument.>

It is proven that monotone circuits computing the perfect matching function on n -vertex graphs require Ω( n ) depth. This implies an exponential gap between the depth of monotone and nonmonotone circuits.

Article Free Access Share on Monotone circuits for matching require linear depth Authors: R. Raz The Hebrew University The Hebrew UniversityView Profile , A. Wigderson The Hebrew University The Hebrew UniversityView Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990 Pages 287–292https://doi.org/10.1145/100216.100253Published:01 April 1990Publication History 35citation224DownloadsMetricsTotal Citations35Total Downloads224Last 12 Months20Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The authors demonstrate an exponential gap between deterministic and probabilistic complexity and between the probabilistic complexity of monotonic and nonmonotonic relations. They then prove, as their main result, an Omega ((log n)/sup 2/) bound on the probabilistic communication complexity of monotonic st-connectivity. From this they deduce that every nonmonotonic NC/sup 1/ circuit for st-connectivity requires a constant fraction of negated input variables.>