אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.