All reports by Author Ran Raz:

__
TR20-087
| 8th June 2020
__

Uma Girish, Ran Raz, Wei Zhan#### Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Revisions: 2

__
TR19-162
| 15th November 2019
__

Ran Raz, Wei Zhan#### The Random-Query Model and the Memory-Bounded Coupon Collector

__
TR19-152
| 6th November 2019
__

Uma Girish, Ran Raz, Avishay Tal#### Quantum versus Randomized Communication Complexity, with Efficient Players

__
TR19-071
| 14th May 2019
__

Sumegha Garg, Ran Raz, Avishay Tal#### Time-Space Lower Bounds for Two-Pass Learning

__
TR18-140
| 11th August 2018
__

Ilan Komargodski, Ran Raz, Yael Tauman Kalai#### A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols

Revisions: 1

__
TR18-107
| 31st May 2018
__

Ran Raz, Avishay Tal#### Oracle Separation of BQP and PH

__
TR17-121
| 31st July 2017
__

Sumegha Garg, Ran Raz, Avishay Tal#### Extractor-Based Time-Space Lower Bounds for Learning

Revisions: 1

__
TR17-020
| 12th February 2017
__

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

__
TR16-113
| 22nd July 2016
__

Gillat Kol, Ran Raz, Avishay Tal#### Time-Space Hardness of Learning Sparse Parities

__
TR16-019
| 5th February 2016
__

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

__
TR15-088
| 31st May 2015
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Communication and External Information

__
TR15-054
| 7th April 2015
__

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein#### Welfare Maximization with Limited Interaction

__
TR14-170
| 10th December 2014
__

Yael Tauman Kalai, Ran Raz#### On the Space Complexity of Linear Programming with Preprocessing

Revisions: 1

__
TR14-113
| 27th August 2014
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Information and Communication for Boolean Functions

__
TR14-049
| 11th April 2014
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Information and Communication

Revisions: 1

__
TR14-023
| 19th February 2014
__

Gil Cohen, Anat Ganor, Ran Raz#### Two Sides of the Coin Problem

Revisions: 1

__
TR13-183
| 22nd December 2013
__

Yael Tauman Kalai, Ran Raz, Ron Rothblum#### How to Delegate Computations: The Power of No-Signaling Proofs

Revisions: 1

__
TR13-107
| 7th August 2013
__

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum#### Efficient Multiparty Protocols via Log-Depth Threshold Formulae

__
TR13-064
| 22nd April 2013
__

Anat Ganor, Ran Raz#### Space Pseudorandom Generators by Communication Complexity Lower Bounds

Revisions: 1

__
TR13-058
| 5th April 2013
__

Ilan Komargodski, Ran Raz, Avishay Tal#### Improved Average-Case Lower Bounds for DeMorgan Formula Size

Revisions: 2

__
TR13-020
| 2nd February 2013
__

Tom Gur, Ran Raz#### Arthur-Merlin Streaming Complexity

__
TR13-001
| 2nd January 2013
__

Gillat Kol, Ran Raz#### Interactive Channel Capacity

Revisions: 1

__
TR12-174
| 12th December 2012
__

Anat Ganor, Ilan Komargodski, Ran Raz#### The Spectrum of Small DeMorgan Formulas

Revisions: 1

__
TR12-062
| 17th May 2012
__

Ilan Komargodski, Ran Raz#### Average-Case Lower Bounds for Formula Size

Revisions: 2

__
TR11-122
| 14th September 2011
__

Gillat Kol, Ran Raz#### Competing Provers Protocols for Circuit Evaluation

__
TR11-096
| 2nd July 2011
__

Gil Cohen, Ran Raz, Gil Segev#### Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification

__
TR10-142
| 18th September 2010
__

Ran Raz, Ricky Rosen#### A Strong Parallel Repetition Theorem for Projection Games on Expanders

__
TR10-035
| 7th March 2010
__

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff#### Pseudorandom Generators for Regular Branching Programs

__
TR10-002
| 4th January 2010
__

Ran Raz#### Tensor-Rank and Lower Bounds for Arithmetic Formulas

__
TR09-138
| 14th December 2009
__

Gillat Kol, Ran Raz#### Bounds on 2-Query Locally Testable Codes with Affine Tests

__
TR09-128
| 29th November 2009
__

Gillat Kol, Ran Raz#### Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist

__
TR08-071
| 6th August 2008
__

Dana Moshkovitz, Ran Raz#### Two Query PCP with Sub-Constant Error

__
TR08-018
| 28th February 2008
__

Ran Raz#### A Counterexample to Strong Parallel Repetition

__
TR08-006
| 18th January 2008
__

Ran Raz, Amir Yehudayoff#### Lower Bounds and Separations for Constant Depth Multilinear Circuits

__
TR08-001
| 5th January 2008
__

Ran Raz#### Elusive Functions and Lower Bounds for Arithmetic Circuits

__
TR07-085
| 2nd September 2007
__

Ran Raz, Amir Yehudayoff#### Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

__
TR07-078
| 11th August 2007
__

Ran Raz, Iddo Tzameret#### Resolution over Linear Equations and Multilinear Proofs

__
TR07-031
| 26th March 2007
__

Yael Tauman Kalai, Ran Raz#### Interactive PCP

__
TR07-026
| 21st November 2006
__

Dana Moshkovitz, Ran Raz#### Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size

__
TR06-087
| 25th July 2006
__

Iordanis Kerenidis, Ran Raz#### The one-way communication complexity of the Boolean Hidden Matching Problem

__
TR06-060
| 4th May 2006
__

Ran Raz, Amir Shpilka, Amir Yehudayoff#### A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

__
TR06-001
| 1st January 2006
__

Ran Raz, Iddo Tzameret#### The Strength of Multilinear Proofs

__
TR05-109
| 28th September 2005
__

Ariel Gabizon, Ran Raz, Ronen Shaltiel#### Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed

__
TR05-108
| 28th September 2005
__

Ariel Gabizon, Ran Raz#### Deterministic Extractors for Affine Sources over Large Fields

__
TR05-086
| 14th August 2005
__

Dana Moshkovitz, Ran Raz#### Sub-Constant Error Low Degree Test of Almost Linear Size

Revisions: 1

__
TR05-038
| 10th April 2005
__

Ran Raz#### Quantum Information and the PCP Theorem

__
TR05-025
| 20th February 2005
__

Zeev Dvir, Ran Raz#### Analyzing Linear Mergers

__
TR04-099
| 11th November 2004
__

Ran Raz#### Extractors with Weak Random Seeds

__
TR04-042
| 21st May 2004
__

Ran Raz#### Multilinear-$NC_1$ $\ne$ Multilinear-$NC_2$

__
TR03-067
| 14th August 2003
__

Ran Raz#### Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size

__
TR02-023
| 16th April 2002
__

Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal#### Bounded-depth Frege lower bounds for weaker pigeonhole principles

Revisions: 1

__
TR02-012
| 3rd February 2002
__

Ran Raz#### On the Complexity of Matrix Product

__
TR01-021
| 7th March 2001
__

Ran Raz#### Resolution Lower Bounds for the Weak Pigeonhole Principle

Revisions: 1

__
TR00-044
| 26th June 2000
__

Tzvika Hartman, Ran Raz#### On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors

__
TR00-029
| 30th April 2000
__

Ran Raz, Amir Shpilka#### Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates

Revisions: 1

__
TR99-046
| 17th November 1999
__

Ran Raz, Omer Reingold, Salil Vadhan#### Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

__
TR98-066
| 3rd November 1998
__

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra#### PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

__
TR97-054
| 17th November 1997
__

Ran Raz, GĂˇbor Tardos, Oleg Verbitsky, Nikolay Vereshchagin#### Arthur-Merlin Games in Boolean Decision Trees

__
TR10-141
| 18th September 2010 (removed)
__

Ran Raz#### A Strong Parallel Repetition Theorem for Projection Games on Expanders

Reason: This paper has been remove on the author's behalf. Please note that TR10-142 is the corrected version.

Uma Girish, Ran Raz, Wei Zhan

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\times n$ contraction matrix $A$, and a parameter $T \leq poly(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive ... more >>>

Ran Raz, Wei Zhan

We study a new model of space-bounded computation, the {\it random-query} model. The model is based on a branching-program over input variables $x_1,\ldots,x_n$. In each time step, the branching program gets as an input a random index $i \in \{1,\ldots,n\}$, together with the input variable $x_i$ (rather than querying an ... more >>>

Uma Girish, Ran Raz, Avishay Tal

We study a new type of separation between quantum and classical communication complexity which is 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. More precisely, we give an explicit partial Boolean ... more >>>

Sumegha Garg, Ran Raz, Avishay Tal

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 [Raz16,KRT17,Raz17,MM18,BOGY18,GRT18]. For example, any algorithm for learning parities of size $n$ requires either a memory of size $\Omega(n^{2})$ or an exponential number ... more >>>

Ilan Komargodski, Ran Raz, Yael Tauman Kalai

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

Ran Raz, Avishay Tal

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(\log N)$, that distinguishes between $D$ and the uniform distribution with advantage $\Omega(1/\log N)$.

(2) No Boolean circuit of $\mathrm{quasipoly}(N)$ ...
more >>>

Sumegha Garg, Ran Raz, Avishay Tal

A matrix $M: A \times X \rightarrow \{-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) \ldots$, where for every $i$, $a_i \in A$ is chosen ... more >>>

Ran Raz

We prove a general time-space 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 ... more >>>

Gillat Kol, Ran Raz, Avishay Tal

We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ 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 ... more >>>

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 and shows that for some learning problems a large storage space is crucial.

More formally, in the problem of ... more >>>

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 [Bra13]. Previously, only a separation of communication complexity and internal information complexity was known [GKR14,GKR15].

More precisely, we obtain an explicit example of a search problem with ... more >>>

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$, ...
more >>>

Yael Tauman Kalai, Ran Raz

Linear Programs are abundant in practice, and tremendous effort has been put into designing efficient algorithms for such problems, resulting with very efficient (polynomial time) algorithms. A fundamental question is: what is the space complexity of Linear Programming?

It is widely believed that (even approximating) Linear Programming requires a large ... more >>>

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 $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol for a partial boolean function cannot always be compressed to ... more >>>

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 $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of ... more >>>

Gil Cohen, Anat Ganor, Ran Raz

In the Coin Problem, one is given n independent flips of a coin that has bias $\beta > 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 ... more >>>

Yael Tauman Kalai, Ran Raz, Ron 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. ... more >>>

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

We put forward a new approach for the design of efficient multiparty protocols:

1. Design a protocol for a small number of parties (say, 3 or 4) which achieves

security against a single corrupted party. Such protocols are typically easy

to construct as they may employ techniques that do not ...
more >>>

Anat Ganor, Ran Raz

In 1989, Babai, Nisan and Szegedy [BNS92] 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 $2^{\Theta(\sqrt n)}\,\,\,$, because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for ... more >>>

Ilan Komargodski, Ran Raz, Avishay Tal

We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every deMorgan 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. 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 ... more >>>

Tom Gur, Ran Raz

We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical $\mathcal{AM}$ streaming algorithm for a wide 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.

... more >>>Gillat Kol, Ran Raz

We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ 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 $\epsilon$, where ... more >>>

Anat Ganor, Ilan Komargodski, Ran Raz

We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size $s$ is concentrated on coefficients of degree up to ... more >>>

Ilan Komargodski, Ran Raz

We give an explicit function $h:\{0,1\}^n\to\{0,1\}$ such that any deMorgan formula of size $O(n^{2.499})$ agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). Previous lower bounds for formula size were obtained for exact computation.

The same ... more >>>

Gillat Kol, Ran Raz

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

Gil Cohen, Ran Raz, Gil Segev

Motivated by the classical problem of privacy amplification, Dodis and Wichs (STOC '09) 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 \times \{0,1\}^d \rightarrow \{0,1\}^m$ that takes two inputs: a weak source $W$ and ... more >>>

Ran Raz, Ricky Rosen

The parallel repetition theorem states that for any Two

Prover Game with value at most $1-\epsilon$ (for $\epsilon<1/2$),

the value of the game repeated $n$ times in parallel is at most

$(1-\epsilon^3)^{\Omega(n/s)}$, where $s$ is the length of the

answers of the two provers. For Projection

Games, the bound on ...
more >>>

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

We give new pseudorandom generators for \emph{regular} read-once branching programs of small width.

A branching program is regular if the in-degree of every vertex in it is (0 or) $2$.

For every width $d$ and length $n$,

our pseudorandom generator uses a seed of length $O((\log d + \log\log n ...
more >>>

Ran Raz

We show that any explicit example for a tensor $A:[n]^r \rightarrow \mathbb{F}$ with tensor-rank

$\geq n^{r \cdot (1- o(1))}$,

(where $r = r(n) \leq \log n / \log \log n$), implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over $\mathbb{F}$. This shows that strong enough ...
more >>>

Gillat Kol, Ran Raz

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field F, with codeword testers that only use tests of the form $av_i + bv_j = c$, where v is ... more >>>

Gillat Kol, Ran Raz

The Unique Games Conjecture (UGC) is possibly the most 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 ... more >>>

Dana Moshkovitz, Ran Raz

We show that the NP-Complete language 3Sat has a PCP

verifier 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

more >>>

Ran Raz

The parallel repetition theorem states that for any two-prover game,

with value $1- \epsilon$ (for, say, $\epsilon \leq 1/2$), the value of

the game repeated in parallel $n$ times is at most

$(1- \epsilon^c)^{\Omega(n/s)}$, where $s$ is the answers' length

(of the original game) and $c$ is a universal ...
more >>>

Ran Raz, Amir Yehudayoff

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

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

$G:C^{m-1} ---> C^m$ ...
more >>>

Ran Raz, Amir Yehudayoff

We study multilinear formulas, monotone arithmetic circuits, maximal-partition discrepancy, best-partition communication complexity and extractors constructions. We start by proving lower bounds for an explicit polynomial for the following three subclasses of syntactically multilinear arithmetic formulas over the field C and the set of variables {x1,...,xn}:

1. Noise-resistant. A syntactically multilinear ... more >>>

Ran Raz, Iddo Tzameret

We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead of clauses. We demonstrate polynomial-size refutations for hard tautologies like the pigeonhole principle, Tseitin graph tautologies and the clique-coloring tautologies in these proof systems. ... more >>>

Yael Tauman Kalai, Ran Raz

An interactive-PCP (say, for the membership $x \in L$) is a

proof that can be verified by reading only one of its bits, with the

help of a very short interactive-proof.

We show that for membership in some languages $L$, there are

interactive-PCPs that are significantly shorter than the known

more >>>

Dana Moshkovitz, Ran Raz

We show a construction of a PCP with both sub-constant error and

almost-linear size. Specifically, for some constant alpha in (0,1),

we construct a PCP verifier for checking satisfiability of

Boolean formulas that on input of size n uses log n + O((log

n)^{1-alpha}) random bits to query a constant ...
more >>>

Iordanis Kerenidis, Ran Raz

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for ... more >>>

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.

Ran Raz, Iddo Tzameret

We introduce an algebraic proof system that manipulates multilinear arithmetic formulas. We show that this proof system is fairly strong, even when restricted to multilinear arithmetic formulas of a very small depth. Specifically, we show the following:

1. Algebraic proofs manipulating depth 2 multilinear arithmetic formulas polynomially simulate Resolution, Polynomial ... more >>>

Ariel Gabizon, Ran Raz, Ronen Shaltiel

An $(n,k)$-bit-fixing source is a distribution $X$ over $\B^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:\B^n

\ar \B^m$ which on ...
more >>>

Ariel Gabizon, Ran Raz

An $(n,k)$-affine source over a finite field $F$ is a random

variable $X=(X_1,...,X_n) \in F^n$, which is uniformly

distributed over an (unknown) $k$-dimensional affine subspace of $

F^n$. We show how to (deterministically) extract practically all

the randomness from affine sources, for any field of size larger

than $n^c$ (where ...
more >>>

Dana Moshkovitz, Ran Raz

Given a function f:F^m \rightarrow F over a finite

field F, a low degree tester tests its proximity to

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

Ran Raz

We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$

by a single quantum state $|\Psi \rangle$ of size $O(n)$ qubits,

such that:

for any constant $k$ and any $i_1,...,i_k \in \{1,...,2^n\}$,

the values of the bits $a_{i_1},...,a_{i_k}$ can be retrieved

from $|\Psi \rangle$ by a one-round Arthur-Merlin interactive ...
more >>>

Zeev Dvir, Ran Raz

Mergers are functions that transform k (possibly dependent)

random sources into a single random source, in a way that ensures

that if one of the input sources has min-entropy rate $\delta$

then the output has min-entropy rate close to $\delta$. Mergers

have proven to be a very useful tool in ...
more >>>

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.

We also give improved constructions of mergers and condensers.

In all that comes below, $\delta$ is an ...
more >>>

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_1,...,x_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^2 ...
more >>>

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 \times n$ matrix is of size super-polynomial

in $n$.

Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal

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

Ran Raz

We prove 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 doesn't

use products with field elements of absolute value larger than 1

(where $m \times m$ is ...
more >>>

Ran Raz

We prove that any Resolution proof for the weak

pigeon hole principle, with $n$ holes and any number of

pigeons, is of length $\Omega(2^{n^{\epsilon}})$,

(for some global constant $\epsilon > 0$).

Tzvika Hartman, Ran Raz

Weak designs were defined by Raz, Reingold and Vadhan (1999) and are

used in constructions of extractors. Roughly speaking, a weak design

is a collection of subsets satisfying some near-disjointness

properties. Constructions of weak designs with certain parameters are

given in [RRV99]. These constructions are explicit in the sense that

more >>>

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, constant depth

threshold circuits ...
more >>>

Ran Raz, Omer Reingold, Salil Vadhan

We give explicit constructions of extractors which work for a source of

any min-entropy on strings of length n. These extractors can extract any

constant fraction of the min-entropy using O(log^2 n) additional random

bits, and can extract all the min-entropy using O(log^3 n) additional

random bits. Both of these ...
more >>>

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

This paper strengthens the low-error PCP characterization of NP, coming

closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for

membership in any NP language can be verified with a constant

number of accesses, and with an error probability exponentially

small in the ...
more >>>

Ran Raz, GĂˇbor Tardos, Oleg Verbitsky, Nikolay Vereshchagin

It is well known that probabilistic boolean decision trees

cannot be much more powerful than deterministic ones (N.~Nisan, SIAM

Journal on Computing, 20(6):999--1007, 1991). Motivated by a question

if randomization can significantly speed up a nondeterministic

computation via a boolean decision tree, we address structural

properties of Arthur-Merlin games ...
more >>>

Ran Raz

Reason: This paper has been remove on the author's behalf. Please note that TR10-142 is the corrected version.