Subspace evasive sets

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

Download

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1hq18

Full metadata record

DC Field	Value	Language
dc.contributor.author	Dvir, Zeev	-
dc.contributor.author	Lovett, S	-
dc.date.accessioned	2018-07-20T15:07:07Z	-
dc.date.available	2018-07-20T15:07:07Z	-
dc.date.issued	2012-05-19	en_US
dc.identifier.citation	Dvir, Z, Lovett, S. (2012). Subspace evasive sets. 351 - 358. doi:10.1145/2213977.2214010	en_US
dc.identifier.uri	http://arks.princeton.edu/ark:/88435/pr1hq18	-
dc.description.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.	en_US
dc.format.extent	351 - 358	en_US
dc.language.iso	en_US	en_US
dc.relation.ispartof	44th Annual ACM Symposium on Theory of Computing, STOC '12	en_US
dc.rights	Author's manuscript	en_US
dc.title	Subspace evasive sets	en_US
dc.type	Conference Article	en_US
dc.identifier.doi	doi:10.1145/2213977.2214010	-
dc.date.eissued	2012	en_US
pu.type.symplectic	http://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceeding	en_US

Files in This Item:

File	Description	Size	Format
Subspace evasive sets.pdf		180 kB	Adobe PDF	View/Download