Volume 2014
Article 9
Published by the Department of Computer Science, The University of Chicago.
A Note on Subspace Evasive Sets
Avraham BenAroya
Department of Computer Science
Weizman Institute of Science
Rehovot, Israel
avraham DOT benaroya 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 lowdimensional 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 capacityachieving listdecodable 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
listdecodable 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áriSósTurá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.
Article 8
Article 10
Volume 2014
Published articles