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 study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001). Our main technical result is ... 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 >>>