We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call \emph{restriction access}. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On ... more >>>

In this work we describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed subspace-evasive sets, started in the work of Pudlak and Rodl (2004) who ... more >>>

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of ... more >>>

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic
self-correcting algorithm that, with high probability, can correct any coordinate of the
codeword by looking at only a few other coordinates, even if a fraction $\delta$ of the
coordinates are corrupted. LCC's are a stronger form ... more >>>

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):
Given a low-degree polynomial mapping
$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy
$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

A $(q,k,t)$-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most $q$ non-zeros, each column has at least $k$ non-zeros and the supports of every two columns intersect in at most t rows. We prove that the rank ... more >>>

An $(r,\delta,\epsilon)$-locally decodable code encodes a $k$-bit message $x$ to an $N$-bit codeword $C(x),$ such that for every $i\in [k],$ the $i$-th message bit can be recovered with probability $1-\epsilon,$ by a randomized decoding procedure that reads only $r$ bits, even if the codeword $C(x)$ is corrupted in up to ... 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 >>>

We describe a new approach for the problem of finding {\rm rigid} matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and ... more >>>

The finite field Kakeya problem deals with the way lines in different directions can overlap in a vector space over a finite field. This problem came up in the study of certain Euclidean problems and, independently, in the search for explicit randomness extractors. We survey recent progress on this problem ... more >>>

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom
generator that fools degree $k$ polynomials over $\F_2$ for an arbitrary
constant $k$. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read $k$ bits of inputs at a
time. This ... more >>>

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.
\begin{enumerate}
\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ... 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 >>>

An algebraic source is a random variable distributed
uniformly over the set of common zeros of one or more multivariate
polynomials defined over a finite field $F$. Our main result is
the construction of an explicit deterministic extractor for
algebraic sources over exponentially large prime fields. More
precisely, we give ... more >>>

A Noisy Interpolating Set (NIS) for degree $d$ polynomials is a
set $S \subseteq \F^n$, where $\F$ is a finite field, such that
any degree $d$ polynomial $q \in \F[x_1,\ldots,x_n]$ can be
efficiently interpolated from its values on $S$, even if an
adversary corrupts a constant fraction of the values. ... more >>>

In this paper we study the problem of explicitly constructing a
{\em dimension expander} raised by \cite{BISW}: Let $\mathbb{F}^n$
be the $n$ dimensional linear space over the field $\mathbb{F}$.
Find a small (ideally constant) set of linear transformations from
$\F^n$ to itself $\{A_i\}_{i \in I}$ such that for every linear
more >>>

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x_1,...,x_m) that cannot be computed by a depth d arithmetic circuit of small size then there exists an ... 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 >>>

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

In this work we study two seemingly unrelated notions. Locally Decodable Codes(LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing ... more >>>

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