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: Simple Affine Extractors using Dimension Expansion
event speaker icon
Ariel Gabizon (Faculty of Mathematics and Computer Science The Weizmann Institute of Science)
event date icon
Wednesday, 30.12.2009, 12:30
event location icon
Taub 201
Let F be the finite field of q elements. An (n,k)-affine extractor is a coloring of F^n with 2 colors, such that every affine subspace of dimension at least k in F^n is colored in a balanced way. Roughly speaking, the problem of explicitly constructing affine extractors gets harder as the field size q gets smaller and easier as k gets larger. In this work, we construct affine extractors whenever q = \Omega( (n/k)^2), provided that F has characteristic \Omega(n/k). For a wide range of parameters this is a new result, but even in ranges of parameters where we do not improve or match known results, we believe our construction and proof have the advantage of being very simple. Our proof uses a result of Heur, Leung, and Xiang about the dimension of products of subspaces. I will present this result of [HLX] in the hope that it could be useful elsewhere in combinatorics and theoretical computer science.