Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field $\mathbb{F}$ of characteristic zero. We resolve this problem by proving a $N^{\Omega(\frac{d}{\tau})}$ lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin ... more >>>

We prove that the Fourier dimension of any Boolean function with
Fourier sparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof
method yields an improved bound of $\widetilde{O}(\sqrt{s})$
assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every
Boolean function of sparsity $s$ there is an affine subspace of
more >>>

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes.

Fix a finite field $\mathbb{F}$. ... more >>>