期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Let \F be the field of q elements. An \emph{\afsext{n}{k}} is a mapping D : \F n \ar \B such that for any k -dimensional affine subspace X \F n , D ( x ) is an almost unbiased bit when x is chosen uniformly from X . Loosely speaking, the problem of explicitly constructing affine extractors gets harder as q gets smaller and easier as k gets larger. This is reflected in previous results: When q is `large enough', specifically q = ( n 2 ) , Gabizon and Raz \cite{GR05} construct affine extractors for any k 1 . In the `hardest case', i.e. when q = 2 , Bourgain \cite{Bour05} constructs affine extractors for k n for any constant (and even slightly sub-constant) 0"> 0 . Our main result is the following: Fix any k 2 and let d = 5 n k . Then whenever 2\cdot d^2"> q 2 d 2 and d"> p = c ha r ( \F ) d , we give an explicit \afsext{n}{k}. For example, when k = n for constant 0"> 0 , we get an extractor for a field of constant size ( 1 2 ) . Thus our result may be viewed as a `field-size/dimension' tradeoff for affine extractors. Although for large k we are not able to improve (or even match) the previous result of \cite{Bour05}, our construction and proof have the advantage of being very simple: Assume n is prime and d is odd, and fix any non-trivial linear map T : \F n \F . Define Q R : \F \B by Q R ( x ) = 1 if and only if x is a quadratic residue. Then, the function D : \F n \B defined by D ( x ) \triangleq Q R ( T ( x d )) is an \afsext{n}{k}. Our proof uses a result of Heur, Leung and Xiang \cite{HLX02} giving a lower bound on the dimension of products of subspaces.
\F n , D ( x ) is an almost unbiased bit when x is chosen uniformly from X . Loosely speaking, the problem of explicitly constructing affine extractors gets harder as q gets smaller and easier as k gets larger. This is reflected in previous results: When q is `large enough', specifically q = 
