Volume 2014
Article 9
Published by the Department of Computer Science, The University of Chicago.
A Note on Subspace Evasive Sets
Avraham Ben-Aroya
Department of Computer Science
Weizman Institute of Science
Rehovot, Israel
avraham DOT ben-aroya AT weizman DOT ac DOT il
and
Igor Shinkar
Department of Computer Science
Weizman Institute of Science
Rehovot, Israel
igor DOT shinkar AT weizman DOT ac DOT il
November 29, 2014
Abstract
A subspace evasive set over a field ${\mathbb F}$ is a subset of ${\mathbb F}^n$ that has small
intersection with any low-dimensional affine subspace of ${\mathbb F}^n$.
Interest in subspace evasive sets began in the work of Pudlák and
Rödl (Quaderni di Matematica 2004)
in the context of explicit constructions of Ramsey graphs.
More recently, Guruswami (CCC 2011) showed that obtaining such sets over large fields
can be used to construct capacity-achieving list-decodable codes with a constant list size.
Our results in this note are as follows:
- We provide a construction of subspace evasive sets in ${\mathbb F}^n$
of size $|{\mathbb F}|^{(1-\epsilon)n}$ that intersect any $k$-dimensional
affine subspace of ${\mathbb F}^n$ in at most $(2/\epsilon)^k$ points.
This slightly improves a recent construction of Dvir and Lovett (STOC 2012)
in terms of the intersection size,
who constructed similar sets, but with a bound of $(k/\epsilon)^k$ on the size of the intersection.
Besides having a smaller intersection, our construction is more elementary.
The construction is explicit when $k$ and $\epsilon$ are constants.
This is sufficient in order to explicitly construct the aforementioned
list-decodable codes.
On the other hand, the construction of Dvir and Lovett is explicit in a
stronger sense,
and relies on solving systems of polynomial equations,
while our construction relies on the method of conditional expectation.
-
We use Kövári-Sós-Turán Theorem to show that for a
certain range of parameters the subspace evasive sets obtained using the
probabilistic method are optimal (up to a multiplicative constant factor).
- The article: PDF (227 KB)
- Source material: ZIP (63 KB)
- BibTeX entry for this article (269 bytes)
Submitted July 2, 2013, revised September 26, 2014 and in final form November 3, 2014, published November 29, 2014.
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
Article 8
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
Article 10
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
Volume 2014
Published articles
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif)
Licensed under a Creative Commons Attribution License