Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Subspace Evasive Sets
event speaker icon
Zeev Dvir (Princeton University)
event date icon
Thursday, 05.01.2012, 12:30
event location icon
Taub 601
We describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed 'subspace-evasive' sets, started in the work of Pudlak and Rodl (2004) who showed how such constructions over the binary field can be used to construct explicit Ramsey graphs. More recently, Guruswami (2011) showed that, over large finite fields (of size polynomial in n), subspace evasive sets can be used to obtain explicit list-decodable codes with optimal rate and constant list-size.

We construct subspace evasive sets over large fields (polynomial in n) and use them to derive the applications to list-decodable codes discovered by Guruswami. Our construction employs both combinatoric and algebraic methods.

(Joint work with Shachar Lovett, IAS)