Subspace evasive sets

Zeev Dvir, Shachar Lovett

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages351-358
Number of pages8
DOIs
StatePublished - Jun 26 2012
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • affine varieties
  • list decodable codes
  • pseudo-randomness

Fingerprint Dive into the research topics of 'Subspace evasive sets'. Together they form a unique fingerprint.

  • Cite this

    Dvir, Z., & Lovett, S. (2012). Subspace evasive sets. In STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing (pp. 351-358). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2213977.2214010