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

For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\mathbb{F}^n$ ... more >>>

The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $\varepsilon^2$ has relative distance at least $\frac{1}{2} - O(\varepsilon)$ with high probability. However, it is a major challenge to construct explicit codes with similar parameters.

One hope to ... more >>>