@inproceedings{065a18220c10406f996f334100a97c6b,

title = "Subspace evasive sets",

abstract = "We construct explicit subspace-evasive sets. These are subsets of double-struck F n of size |double-struck 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.",

keywords = "affine varieties, list decodable codes, pseudo-randomness",

author = "Zeev Dvir and Shachar Lovett",

year = "2012",

doi = "10.1145/2213977.2214010",

language = "English (US)",

isbn = "9781450312455",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

pages = "351--358",

booktitle = "STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing",

note = "44th Annual ACM Symposium on Theory of Computing, STOC '12 ; Conference date: 19-05-2012 Through 22-05-2012",

}