Ran Raz

FOCS Conference 2023 Conference Paper

Certified Hardness vs. Randomness for Log-Space

• Edward Pyne
• Ran Raz
• Wei Zhan

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. 1 Our result is stated and proved for promise-BPL, but we ignore this difference in the abstract.

STOC Conference 2023 Conference Paper

Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

• Qipeng Liu 0001
• Ran Raz
• Wei Zhan

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on n bits requires either Ω( n 2 ) 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 Ω( n 2 ) 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 ( a i , b i = M ( a i , x )) where for every i , a i ∈ 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 n 2 bits of classical memory and c n bits of quantum memory (for some constant c >0).

STOC Conference 2022 Conference Paper

Parallel repetition for all 3-player games over binary alphabet

• Uma Girish
• Justin Holmgren
• Kunal Mittal
• Ran Raz
• Wei Zhan

We prove that for every 3-player (3-prover) game, with binary questions and answers and value 0, such that the value of the n -fold parallel repetition of the game is at most n − c . Along the way to proving this theorem, we prove two additional parallel repetition theorems for multiplayer (multiprover) games, that may be of independent interest: Playerwise Connected Games (with any number of players and any Alphabet size): We identify a large class of multiplayer games and prove that for every game with value 0, such that the value of the n -fold parallel repetition of the game is at most 2 − c n . Only inverse Ackermann decay bounds were previously known (Verbitsky 1996). The 3-player anti-correlation game was studied and motivated in several previous works. In particular, Holmgren and Yang (STOC 2019) gave it as an example for a 3-player game whose non-signaling value (is smaller than 1 and yet) does not decrease at all under parallel repetition.

FOCS Conference 2020 Conference Paper

Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms

• Sepehr Assadi
• Ran Raz

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 n 2-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(n 7/6 ) space algorithms, leaving open a large gap between (trivial) upper bounds and lower bounds.

STOC Conference 2019 Conference Paper

Oracle separation of BQP and PH

• Ran Raz
• Avishay Tal

We present a distribution D over inputs in {−1,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 D and the uniform distribution with advantage Ω(1/log N ). (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 . 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 O relative to which BQP O ⊈ PH O .

STOC Conference 2018 Conference Paper

Extractor-based time-space lower bounds for learning

• Sumegha Garg
• Ran Raz
• Avishay Tal

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, ( a 1 , b 1 ), ( a 2 , b 2 ) …, where for every i , a i ∈ 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 learning algorithm for the learning problem corresponding to M requires either a memory of size at least Ω( k · l ), 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, any learning algorithm requires either a memory of size at least Ω((log| X |) · (log| A |)) or an exponential number of samples, achieving a tight Ω((log| X |) · (log| A |)) lower bound on the size of the memory, rather than a bound of Ω(min{(log| X |) 2 ,(log| A |) 2 }) obtained in previous works by Raz [FOCS’17] and Moshkovitz and Moshkovitz [ITCS’18]. Moreover, our result implies all previous memory-samples lower bounds, as well as a number of new applications. Our proof builds on the work of Raz [FOCS’17] that gave a general technique for proving memory samples lower bounds.

FOCS Conference 2017 Conference Paper

A Time-Space Lower Bound for a Large Class of Learning Problems

• Ran Raz

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, (a 1, b 1 ), (a 2, b 2 ). .. , where for every i, a i ∈ A is chosen uniformly at random and b i = M(ai, x). Let σ max be 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 = log 2 |X|. As a special case, this gives a new proof for the memory-samples lower bound for parity learning [14].

STOC Conference 2017 Conference Paper

Time-space hardness of learning sparse parities

• Gillat Kol
• Ran Raz
• Avishay Tal

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. A recent work shows that the class of all parity functions is time-space hard [Raz, FOCS'16]. Building on [Raz, FOCS'16], we show that the class of all sparse parities of Hamming weight ℓ is time-space hard, as long as ℓ ≥ ω(log n / loglog n ). Consequently, linear-size DNF Formulas, linear-size Decision Trees and logarithmic-size Juntas are all time-space hard. Our result is more general and provides time-space lower bounds for learning any concept class of parity functions. We give applications of our results in the field of bounded-storage cryptography. For example, for every ωlog n ) ≤ k ≤ n , we obtain an encryption scheme that requires a private key of length k , and time complexity of n per encryption/decryption of each bit, and is provably and unconditionally secure as long as the attacker uses at most o ( nk ) memory bits and the scheme is used at most 2 o ( k ) times. Previously, this was known only for k = n [Raz, FOCS'16].

STOC Conference 2016 Conference Paper

Exponential separation of communication and external information

• Anat Ganor
• Gillat Kol
• Ran Raz

We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman. Previously, only a separation of communication complexity and internal information complexity was known.

FOCS Conference 2016 Conference Paper

Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

• Ran Raz

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} 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 at is uniformly distributed over {0, 1} n and bt 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 provenly 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.

I&C Journal 2015 Journal Article

Arthur–Merlin streaming complexity

• Tom Gur
• Ran Raz

We study the power of Arthur–Merlin probabilistic proof systems in the data stream model. We show a canonical AM streaming algorithm for a class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it. As an application, we give an AM streaming algorithm for the Distinct Elements problem. Given a data stream of length m over alphabet of size n, the algorithm uses O ˜ ( s ) space and a proof of size O ˜ ( w ), for every s, w such that s ⋅ w ≥ n (where O ˜ hides a polylog ( m, n ) factor). We also prove a lower bound, showing that every MA streaming algorithm for the Distinct Elements problem that uses s bits of space and a proof of size w, satisfies s ⋅ w = Ω ( n ). Furthermore, the lower bound also holds for approximating the number of distinct elements within a multiplicative factor of 1 ± 1 / n. As a part of the proof of the lower bound for the Distinct Elements problem, we show a new lower bound of Ω ( n ) on the MA communication complexity of the Gap Hamming Distance problem, and prove its tightness.

STOC Conference 2015 Conference Paper

Exponential Separation of Information and Communication for Boolean Functions

• Anat Ganor
• Gillat Kol
• Ran Raz

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 ≥ 2 k . 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.

FOCS Conference 2015 Conference Paper

Welfare Maximization with Limited Interaction

• Noga Alon
• Noam Nisan
• Ran Raz
• Omri Weinstein

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 n 1/(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 Ω(n 1/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].

FOCS Conference 2014 Conference Paper

Exponential Separation of Information and Communication

• Anat Ganor
• Gillat Kol
• Ran Raz

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.

STOC Conference 2014 Conference Paper

How to delegate computations: the power of no-signaling proofs

• Yael Tauman Kalai
• Ran Raz
• Ron D. Rothblum

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 MIPs 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). This method relies on the existence of a sub-exponentially secure PIR scheme, and was proved secure by Kalai et al (STOC, 2013) assuming the underlying MIP is secure against no-signaling provers.

STOC Conference 2013 Conference Paper

Average-case lower bounds for formula size

• Ilan Komargodski
• Ran Raz

We give an explicit function h:{0,1} n ->{0,1} such that any deMorgan formula of size O(n 2.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(n 1.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 Ω(n 2.5-o(1) ) formula size lower bound that was proved for the case of exact computation.

STOC Conference 2013 Conference Paper

Delegation for bounded space

• Yael Tauman Kalai
• Ran Raz
• Ron D. Rothblum

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

FOCS Conference 2013 Conference Paper

Improved Average-Case Lower Bounds for DeMorgan Formula Size

• Ilan Komargodski
• Ran Raz
• Avishay Tal

We give an explicit function h: {0, 1} n → {0, 1} such that every deMorgan formula of size n 3-o(1) /r 2 agrees 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 Raz 1.

STOC Conference 2013 Conference Paper

Interactive channel capacity

• Gillat Kol
• Ran Raz

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.

FOCS Conference 2010 Conference Paper

Pseudorandom Generators for Regular Branching Programs

• Mark Braverman
• Anup Rao 0001
• Ran Raz
• Amir Yehudayoff

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.

STOC Conference 2010 Conference Paper

Tensor-rank and lower bounds for arithmetic formulas

• Ran Raz

We show that any explicit example for a tensor A:[n] r -> F with tensor-rank ≥ n r ⋅ (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.

FOCS Conference 2008 Conference Paper

A Counterexample to Strong Parallel Repetition

• Ran Raz

The parallel repetition theorem states that for any two-prover game, with value 1 - isin (for, say, isin les 1/2), the value of the game repeated in parallel n times is at most (1 - isin c ) Omega(n/s), where s is the answers' length (of the original game) and c is a universal constant. Several researchers asked wether this bound could be improved to (1 - isin) Omega(n/s); this question is usually referred to as the strong parallel repetition problem. We show that the answer for this question is negative. More precisely, we consider the odd cycle game of size m; a two-prover game with value 1 - 1/2 m. We show that the value of the odd cycle game repeated in parallel n times is at least 1 - (1/m) ldr O(radicn). This implies that for large enough n (say, n ges Omega(m 2 )), the value of the odd cycle game repeated in parallel n times is at least (1 - 1/4 m 2 ) O(n). Thus: 1. For parallel repetition of general games: the bounds of (1 - isin c ) Omega(n/s) given in are of the right form, up to determining the exact value of the constant c ges 2. 2. For parallel repetition of XOR games, unique games and projection games: the bounds of (1 - isin 2 ) Omega(n) given in (for XOR games) and in (for unique and projection games) are tight. 3. For parallel repetition of the odd cycle game: the bound of 1 - (1/m) ldr Omegatilde(radicn) given in 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 - isin 2 satisfiable from instances that are at most 1 - (2/pi) ldr isin satisfiable. Our results suggest that this cannot be proved just by improving the known bounds on parallel repetition.

STOC Conference 2008 Conference Paper

Elusive functions and lower bounds for arithmetic circuits

• Ran Raz

A basic fact in linear algebra is that the image of the curve f(x)=(x 1 ,x 2 ,x 3 ,...,x m ), say over C, is not contained in any m-1 dimensional affine subspace of C m . In other words, the image of f is not contained in the image of any polynomial-mapping Γ:C m-1 → C m of degree~1 (that is, an affine mapping). Can one give an explicit example for a polynomial curve f:C → C m , such that, the image of f is not contained in the image of any polynomial-mapping Γ:C m-1 → C m 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:F n → F m is (s,r)-elusive , if for every polynomial-mapping Γ:F s → F m 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:F n → F n 2 , of degree O(r), that is (s,r)-elusive for s = n 1+Ω(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 ≥ n 1+Ω(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 ≥ n 1+Ω(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.

FOCS Conference 2008 Conference Paper

Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

• Ran Raz
• Amir Yehudayoff

We study a new method for proving lower bounds for subclasses of arithmetic circuits. Roughly speaking, the lower bound is proved by bounding the correlation between the coefficients' vector of a polynomial and the coefficients' vector of any product of two polynomials with disjoint sets of variables. We prove lower bounds for several old and new subclasses of circuits.

FOCS Conference 2008 Conference Paper

Two Query PCP with Sub-Constant Error

• Dana Moshkovitz
• Ran Raz

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.

FOCS Conference 2007 Conference Paper

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

• Ran Raz
• Amir Shpilka
• Amir Yehudayoff

We construct an explicit polynomial f(x 1, .. ., 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 2 n} The lower bound holds over any field.

STOC Conference 2007 Conference Paper

Exponential separations for one-way quantum communication complexity, with applications to cryptography

• Dmitry Gavinsky
• Julia Kempe
• Iordanis Kerenidis
• Ran Raz
• Ronald de Wolf

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.

STOC Conference 2006 Conference Paper

Sub-constant error low degree test of almost-linear size

• Dana Moshkovitz
• Ran Raz

Given a function f:F m →F over a finite field F, a low degree tester tests its agreement with an m-variate polynomial of total degree at most d over F. The tester is usually given access to an oracle 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 A (say, one query to f and one query to A), and decides whether to accept or reject based on the replies.We wish to minimize two parameters of a 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's queries.Low degree testing is a central ingredient in most constructions of probabilistically checkable proofs (PCPs) and locally testable codes (LTCs). The error of the low degree tester is related to the soundness of the PCP and its size is related to the size of the PCP (or the length of the LTC).We design and analyze new low degree testers that have both sub-constant error o(1) and almost-linear size n 1+o(1) (where n=|F| m ). Previous constructions of sub-constant error testers had polynomial size [13, 16]. These testers enabled the construction of PCPs with sub-constant soundness , but polynomial size [13, 16, 9]. Previous constructions of almost-linear size testers obtained only constant error [13, 7]. These testers were used to construct almost-linear size LTCs and almost-linear size PCPs with constant soundness [13, 7, 5, 6, 8].

FOCS Conference 2006 Conference Paper

Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP

• Yael Tauman Kalai
• Ran Raz

Let Lambda: {0, 1} n times {0, 1} m rarr {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} m be 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 (x 1, y) = z 1, .. ., Lambda(x N, y) = z N by 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(w 1, .. ., w m ) 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(x 1 ) = z 1, .. ., y(x N ) = z N by 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

TCS Journal 2005 Journal Article

A time lower bound for satisfiability

• Dieter van Melkebeek
• Ran Raz

We show that a deterministic Turing machine with one d-dimensional work tape and random access to the input cannot solve satisfiability in time n a for a < ( d + 2 ) / ( d + 1 ). For conondeterministic machines, we obtain a similar lower bound for any a such that a 3 < 1 + a / ( d + 1 ). The same bounds apply to almost all natural NP -complete problems known.

FOCS Conference 2005 Conference Paper

Deterministic Extractors for Affine Sources over Large Fields

• Ariel Gabizon
• Ran Raz

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

STOC Conference 2005 Conference Paper

Extractors with weak random seeds

• Ran Raz

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: A long line of research, starting by Nisan and Zuckerman[14], gives explicit constructions of seeded-extractors, that is, extractors that use a short seed of truly random bits to extract randomness from a weak random source. For every such extractor E , with seed of length d , we construct an extractor E ′, with seed of length d ′= O ( d ), that achieves the same parameters as E but only requires the seed to be of min-entropy larger than (1⁄2+δ) • d ′ (rather than fully random), where δ is an arbitrary small constant. Fundamental results of Chor and Goldreich and Vazirani [6,21] show how to extract Ω( n ) random bits from two (independent) sources of length n and min-entropy larger than (1⁄2δ) • n , where δ is an arbitrary small constant. We show how to extract Ω( n ) random bits (with optimal probability of error) when only one source is of min-entropy (1⁄2+δ) • n and the other source is of logarithmic min entropy. 3 A recent breakthrough of Barak, Impagliazzo and Wigderson[4] shows how to extract Ω( n ) random bits from a constant number of (independent) sources of length n and min-entropy larger than δ n , where δ is an arbitrary small constant. We show how to extract Ω ( n ) random bits (with optimal probability of error) when only one source is of min-entropy δ n and all other (constant number of) sources are of logarithmic min-entropy. A very recent result of Barak, Kindler, Shaltiel, Sudakov and Wigderson[5] shows how to extract a constant number of random bits from three (independent) sources of length n and min-entropy larger than δ n , where δ is an arbitrary small constant. We show how to extract Ω( n )/ random bits, with sub-constant probability of error, from one source of min-entropy δ n and two sources of logarithmic min-entropy. In the same paper, Barak, Kindler, Shaltiel, Sudakov and Wigderson[5] give an explicit coloring of the complete bipartite graph of size 2 n x 2 n with two colors, such that there is no monochromatic subgraph of size larger than 2 δ n x 2 2 δ n , where δ is an arbitrary small constant. We give an explicit coloring of the complete bipartite graph of size 2 n x 2 n with a constant number of colors, such that there is no monochromatic subgraph of size larger than 2 δ n x n 5 . We show that using a constant number of truly random bits, one can condense a source of length n and min-entropy rate δ into a source of length Ω ( n ) and min-entropy rate 1-δ, where δ is an arbitrary small constant. We show that using a constant number of truly random bits, one can merge a constant number of sources of length n , such that at least one of them is of min-entropy rate 1-δ, into one source of length Ω( n ) and min-entropy rate slightly less than 1-δ, where δ is any small constant.

FOCS Conference 2005 Conference Paper

Quantum Information and the PCP Theorem

• Ran Raz

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.

FOCS Conference 2004 Conference Paper

Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed

• Ariel Gabizon
• Ran Raz
• Ronen Shaltiel

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.

STOC Conference 2004 Conference Paper

Multi-linear formulas for permanent and determinant are of super-polynomial size

• Ran Raz

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.

FOCS Conference 2004 Conference Paper

Multilinear-NC neq Multilinear-NC

• Ran Raz

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.

FOCS Conference 2002 Conference Paper

Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles

• Joshua Buresh-Oppenheim
• Paul Beame
• Toniann Pitassi
• Ran Raz
• Ashish Sabharwal

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.

STOC Conference 2002 Conference Paper

On the complexity of matrix product

• Ran Raz

We prove a lower bound of Ω( 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 doesn't use products with field elements of absolute value larger than 1 (where m x m 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 Ω( m 2 log 2c 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.

STOC Conference 2002 Conference Paper

Resolution lower bounds for the weak pigeonhole principle

• Ran Raz

(MATH) We prove that any Resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length ω(2 n ε ), (for some constant ε ρ 0). One corollary is that a certain propositional formulation of the statement NP \not \subset P/poly does not have short Resolution proofs.

SODA Conference 2001 Conference Paper

Distance labeling in graphs

• Cyril Gavoille
• David Peleg
• Stephane Perennes
• Ran Raz

STOC Conference 2001 Conference Paper

Explicit lower bound of 4. 5n - o(n) for boolena circuits

• Oded Lachish
• Ran Raz

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.

STOC Conference 2001 Conference Paper

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates

• Ran Raz
• Amir Shpilka

We prove super-linear 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 super-linear in m^2 (where m \times m is the size of each matrix). That is, the lower bound is super-linear in the number of input variables. Moreover, if the circuit is bilinear the result applies also for the case where the circuit gets for free any product of two linear functions. We show that the number of edges in any constant depth arithmetic circuit for the trace of the product of 3 matrices (over fields with characteristic~0) is super-linear in m^2 . (Note that the trace is a single-output function). We give explicit examples for n Boolean functions f_1,\dots,f_ , such that any constant depth Boolean circuit with arbitrary gates for f_1,...,f_n has a super-linear number of edges. The lower bound is proved also 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.

STOC Conference 2001 Conference Paper

Regular resolution lower bounds for the weak pigeonhole principle

• Toniann Pitassi
• Ran Raz

STOC Conference 2000 Conference Paper

Higher lower bounds on monotone size

• Danny Harnik
• Ran Raz

FOCS Conference 1999 Conference Paper

Error Reduction for Extractors

• Ran Raz
• Omer Reingold
• Salil P. Vadhan

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.

STOC Conference 1999 Conference Paper

Exponential Separation of Quantum and Classical Communication Complexity

• Ran Raz

STOC Conference 1999 Conference Paper

Extracting all the Randomness and Reducing the Error in Trevisan's Extractors

• Ran Raz
• Omer Reingold
• Salil P. Vadhan

STOC Conference 1999 Conference Paper

On Recycling the Randomness of States in Space Bounded Computation

• Ran Raz
• Omer Reingold

STOC Conference 1999 Conference Paper

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

• Irit Dinur
• Eldar Fischer
• Guy Kindler
• Ran Raz
• Muli Safra

STOC Conference 1997 Conference Paper

A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP

• Ran Raz
• Muli Safra

STOC Conference 1997 Conference Paper

Direct Product Results and the GCD Problem, in Old and New Communication Models

• Itzhak Parnafes
• Ran Raz
• Avi Wigderson

FOCS Conference 1997 Conference Paper

No Feasible Interpolation for TC0-Frege Proofs

• Maria Luisa Bonet
• Toniann Pitassi
• Ran Raz

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

FOCS Conference 1997 Conference Paper

Separation of the Monotone NC Hierarchy

• Ran Raz
• Pierre McKenzie

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.

STOC Conference 1995 Conference Paper

A parallel repetition theorem

• Ran Raz

STOC Conference 1995 Conference Paper

Lower bounds for cutting planes proofs with small coefficients

• Maria Luisa Bonet
• Toniann Pitassi
• Ran Raz

FOCS Conference 1993 Conference Paper

On the "log rank"-Conjecture in Communication Complexity

• Ran Raz
• Boris Spieker

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

STOC Conference 1990 Conference Paper

Monotone Circuits for Matching Require Linear Depth

• Ran Raz
• Avi Wigderson

FOCS Conference 1989 Conference Paper

Probabilistic Communication Complexity of Boolean Relations (Extended Abstract)

• Ran Raz
• Avi Wigderson

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