This paper extends Valiant's work on $\vp$ and $\vnp$ to the settings in which variables are not multiplicatively commutative and/or associative. Our main result is a theory of completeness for these algebraic worlds. We define analogs of Valiant's classes $\vp$ and $\vnp$, as well as of the polynomials permanent and ... more >>>

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a distribution $X$ on binary strings of length $n$ is a $\delta$-source if $X$ assigns probability at most $2^{-\delta n}$ to any string of length $n$. For every $\delta>0$ we construct the following poly($n$)-time ... more >>>

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that ... more >>>

The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to: (1) Constant degree dimension expanders in finite ... more >>>

The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)). This basic construct underlies “hardness amplification” in cryptography, circuit complexity and PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent result by Dinur and ... more >>>

We study solution sets to systems of generalized linear equations of the following form: $\ell_i (x_1, x_2, \cdots , x_n)\, \in \,A_i \,\, (\text{mod } m)$, where $\ell_1, \ldots ,\ell_t$ are linear forms in $n$ Boolean variables, each $A_i$ is an arbitrary subset of $\mathbb{Z}_m$, and $m$ is a composite ... more >>>

The classical Direct-Product Theorem for circuits says that if a Boolean function $f:\{0,1\}^n\to\{0,1\}$ is somewhat hard to compute on average by small circuits, then the corresponding $k$-wise direct product function $f^k(x_1,\dots,x_k)=(f(x_1),\dots,f(x_k))$ (where each $x_i\in\{0,1\}^n$) is significantly harder to compute on average by slightly smaller circuits. We prove a \emph{fully uniform} ... more >>>

A merger is a probabilistic procedure which extracts the randomness out of any (arbitrarily correlated) set of random variables, as long as one of them is uniform. Our main result is an efficient, simple, optimal (to constant factors) merger, which, for $k$ random vairables on $n$ bits each, uses a ... more >>>

Any proof of P!=NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier ... more >>>

In this paper we study the one-way multi-party communication model, in which every party speaks exactly once in its turn. For every fixed $k$, we prove a tight lower bound of $\Omega{n^{1/(k-1)}}$ on the probabilistic communication complexity of pointer jumping in a $k$-layered tree, where the pointers of the $i$-th ... more >>>

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>>

Ahlswede and Winter introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan). As a consequence, we derandomize a construction of Alon ... more >>>

In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter, in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is ... more >>>

For every $\epsilon>0$, we present a {\em deterministic}\/ log-space algorithm that correctly decides undirected graph connectivity on all but at most $2^{n^\epsilon}$ of the $n$-vertex graphs. The same holds for every problem in Symmetric Log-space (i.e., $\SL$). Making no assumptions (and in particular not assuming the ERH), we present a ... more >>>

We continue the investigation of interactive proofs with bounded communication, as initiated by Goldreich and Hastad (IPL 1998). Let $L$ be a language that has an interactive proof in which the prover sends few (say $b$) bits to the verifier. We prove that the complement $\bar L$ has a {\em ... more >>>

The main contribution of this work is a new type of graph product, which we call the zig-zag product. Taking a product of a large graph with a small graph, the resulting graph inherits (roughly) its size from the large one, its degree from the small one, and its expansion ... more >>>

On an input probability distribution with some (min-)entropy an {\em extractor} outputs a distribution with a (near) maximum entropy rate (namely the uniform distribution). A natural weakening of this concept is a condenser, whose output distribution has a higher entropy rate than the input distribution (without losing much of the ... more >>>

In the theory of pseudorandomness, potential (uniform) observers are modeled as probabilistic polynomial-time machines. In fact many of the central results in that theory are proven via probabilistic polynomial-time reductions. In this paper we show that analogous deterministic reductions are unlikely to hold. We conclude that randomness of the observer ... more >>>

We call a pseudorandom generator $G_n:\{0,1\}^n\to \{0,1\}^m$ {\em hard} for a propositional proof system $P$ if $P$ can not efficiently prove the (properly encoded) statement $G_n(x_1,\ldots,x_n)\neq b$ for {\em any} string $b\in\{0,1\}^m$. We consider a variety of ``combinatorial'' pseudorandom generators inspired by the Nisan-Wigderson generator on the one hand, and ... more >>>

We give the first construction of a pseudo-random generator with optimal seed length that uses (essentially) arbitrary hardness. It builds on the novel recursive use of the NW-generator in a previous paper by the same authors, which produced many optimal generators one of which was pseudo-random. This is achieved in ... more >>>

We present the best known separation between tree-like and general resolution, improving on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}. This is done by constructing a natural family of contradictions, of size $n$, that have $O(n)$-size resolution refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations. This result implies that the most ... more >>>

A hitting-set generator is a deterministic algorithm which generates a set of strings that intersects every dense set recognizable by a small circuit. A polynomial time hitting-set generator readily implies $RP=P$. Andreev \etal\/ (ICALP'96, and JACM 1998) showed that if polynomial-time hitting-set generator in fact implies the much stronger conclusion ... more >>>

We study space complexity in the framework of propositional proofs. We consider a natural model analogous to Turing machines with a read-only input tape, and such popular propositional proof systems as Resolution, Polynomial Calculus and Frege systems. We propose two different space measures, corresponding to the maximal number of bits, ... more >>>

In this paper we prove near quadratic lower bounds for depth-3 arithmetic formulae over fields of characteristic zero. Such bounds are obtained for the elementary symmetric functions, the (trace of) iterated matrix multiplication, and the determinant. As corollaries we get the first nontrivial lower bounds for computing polynomials of constant ... more >>>

The width of a Resolution proof is defined to be the maximal number of literals in any clause of the proof. In this paper we relate proof width to proof length (=size), in both general Resolution, and its tree-like variant. The following consequences of these relations reveal width as a ... more >>>

This paper initiates the study of deterministic amplification of space bounded probabilistic algorithms. The straightforward implementations of known amplification methods cannot be used for such algorithms, since they consume too much space. We present a new implementation of the Ajtai-Koml\'{o}s-Szemer\'{e}di method, that enables to amplify an $S$ space algorithm that ... more >>>

We consider the size of circuits which perfectly hash an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$ into $\bitset^m$. We observe that, in general, the size of such circuits is exponential in $2k-m$, and provide a matching upper bound. more >>>

more >>>

This paper provides logspace and small circuit depth analogs of the result of Valiant-Vazirani, which is a randomized (or nonuniform) reduction from NP to its arithmetic analog ParityP. We show a similar randomized reduction between the Boolean classes NL and semi-unbounded fan-in Boolean circuits and their arithmetic counterparts. These reductions ... more >>>

We present three explicit constructions of hash functions, which exhibit a trade-off between the size of the family (and hence the number of random bits needed to generate a member of the family), and the quality (or error parameter) of the pseudo-random property it achieves. Unlike previous constructions, most notably ... more >>>

This paper concerns the open problem of Lovasz and Saks regarding the relationship between the communication complexity of a boolean function and the rank of the associated matrix. We first give an example exhibiting the largest gap known. We then prove two related theorems. more >>>