We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over \F.
We prove that, with very high probability, a random degree d polynomial has only an exponentially small correlation with all polynomials of degree d-1, for all degrees d up to ... more >>>

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals 1 - 2/q over any field F_q where q > 2. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree 2. Previously, tight bounds ... more >>>

A distance estimator is a code together with a randomized algorithm. The algorithm approximates the distance of any word from the code by making a small number of queries to the word. One such example is the Reed-Muller code equipped with an appropriate algorithm. It has polynomial length, polylogarithmic alphabet ... more >>>

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been ... more >>>

We consider the problem of testing if a given function f : \F_q^n \rightarrow \F_q is close to a n-variate degree d polynomial over the finite field \F_q of q elements. The natural, low-query, test for this property would be to pick the smallest dimension t = t_{q,d}\approx d/q such ... more >>>

Decomposition theorems in classical Fourier analysis enable us to express a bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases. The Goldreich-Levin algorithm can be viewed as an algorithmic analogue of such a decomposition as it ... more >>>

We develop new techniques to incorporate the recently proposed ``short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical ``Label Cover + Fourier Analysis'' framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs ... more >>>

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length N and distance d is known to ... more >>>

We study the following natural question on random sets of points in \mathbb{F}_2^m:

Given a random set of k points Z=\{z_1, z_2, \dots, z_k\} \subseteq \mathbb{F}_2^m, what is the dimension of the space of degree at most r multilinear polynomials that vanish on all points in Z?

We ... more >>>

We prove that random low-degree polynomials (over \mathbb{F}_2) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, ... more >>>