דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Simple Affine Extractors using Dimension Expansion
event speaker icon
אריאל גביזון (מכון ויצמן)
event date icon
יום רביעי, 30.12.2009, 12:30
event location icon
טאוב 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.
[בחזרה לאינדקס האירועים]