科研之友
微信
新浪微博
Facebook
分享链接
摘要
Dispersers and extractors for affine sources of dimension d in F-2(m)-where F-2 denotes the finite field of size 2-are functions f : F-2(m) -%26gt; F-2 that behave pseudorandomly when their domain is restricted to any particular affine space S subset of F-2(m) of dimension at least d. For dispersers, %26quot;pseudorandom behavior%26quot; means that f is nonconstant over S, i.e., {f(s) vertical bar s is an element of S} = F-2. For extractors, it means that f(s) is distributed almost uniformly over F-2 when s is distributed uniformly over S. Dispersers and extractors for affine sources have been considered in the context of deterministic extraction of randomness from structured sources of imperfect randomness. Previously, explicit constructions of affine dispersers were known for every d = Omega(m) (due to [B. Barak et al., in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2005]), and explicit affine extractors for the same dimensions were obtained by [J. Bourgain, Geom. Funct. Anan., 17 (2007), pp. 33-57]. The main result of this paper is an efficient deterministic construction of affine dispersers for sublinear dimension d = O(m(4/5)). We also construct analogous objects over F-p for prime p. Additional results include a new and simple affine extractor for dimension d %26gt; 2m/5 and a simple disperser for multiple independent affine sources. The main novelty in this paper lies in the method of proof, which makes use of classical algebraic objects called subspace polynomials. In contrast, the papers mentioned above relied on the sum-product theorem for finite fields and other recent results from additive combinatorics.
- 出版日期2012
