{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>>

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon > 0$, we prove that with high probability a random subspace $C$ of $\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the property that every Hamming ball of radius $pn$ has at most $O(1/\varepsilon)$ codewords. This answers a basic open question concerning ... more >>>

In this paper, we give surprisingly efficient algorithms for list-decoding and testing {\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable in the {\em high-error} regime with only a {\em constant} number of queries. More precisely, we show that for ... more >>>

We consider the problem of testing if a given function $f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial in $n$ variables, also known as the Reed-Muller testing problem. Alon et al.~\cite{AKKLR} proposed and analyzed a natural $2^{d+1}$-query test for this property and showed that it accepts ... more >>>

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... 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 >>>

Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>