Skip to main content

Subspace evasive sets

Author(s): Dvir, Zeev; Lovett, S

To refer to this page use:
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.
Publication Date: 19-May-2012
Electronic Publication Date: 2012
Citation: Dvir, Z, Lovett, S. (2012). Subspace evasive sets. 351 - 358. doi:10.1145/2213977.2214010
DOI: doi:10.1145/2213977.2214010
Pages: 351 - 358
Type of Material: Conference Article
Journal/Proceeding Title: 44th Annual ACM Symposium on Theory of Computing, STOC '12
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.