Subspace evasive sets

We construct explicit subspace-evasive sets. These are subsets of F n of size |F| (1-ε)n whose intersection with any k-dimensional subspace is bounded by a constant c(k,ε). This problem was raised by Guruswami (CCC 2011) as it leads to optimal rate list-decodable codes of constant list size. The main technical ingredient is the construction of k low-degree polynomials whose common set of zeros has small intersection with any k-dimensional subspace.

Authors

• Zeev Dvir
• Shachar Lovett

Keywords

• affine varieties
• list decodable codes
• pseudo-randomness