Chicago Journal of Theoretical Computer Science

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:
DOI: 10.4086/cjtcs.2014.009


[] Article 8 [] Article 10
[back] Volume 2014 [back] Published articles
[CJCTS home]