摘要
An affine extractor is a map that is balanced on every affine subspace of large enough dimension. We construct an explicit affine extractor AE from F(n) to F, F a prime field, so that AE( x) is exponentially close to uniform when x is chosen uniformly at random from an arbitrary affine subspace of Fn of dimension at least delta n, 0<delta <= 1 a constant. Previously, Bourgain constructed such affine extractors when the size of F is two. Our construction is in the spirit of but different than Bourgain's construction. This allows for simpler analysis and better quantitative results.
- 出版日期2011-3