Events
The Taub Faculty of Computer Science Events and Talks
Ariel Gabizon (Faculty of Mathematics and Computer Science The Weizmann Institute of Science)
Wednesday, 30.12.2009, 12:30
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.