文章基本信息

标题：A Note on Subspace Evasive Sets
本地全文：下载
作者：Avraham Ben-Aroya ; Igor Shinkar
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2014
卷号：2014
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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).