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

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