Affine dispersers from subspace polynomials

Eli Ben-Sasson, Swastik Kopparty

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

Dispersers and extractors for affine sources of dimension d in F m 2-where F 2 denotes the finite field of size 2-are functions f: F m 2 → F 2 that behave pseudorandomly when their domain is restricted to any particular affine space S ⊆ F m 2 of dimension at least d. For dispersers, "pseudorandom behavior" means that f is nonconstant over S, i.e., {f(s) | s ∈ 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 = Ω(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 > 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.

Original languageEnglish (US)
Pages (from-to)880-914
Number of pages35
JournalSIAM Journal on Computing
Volume41
Issue number4
DOIs
StatePublished - 2012

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Keywords

  • Affine extractors
  • Derandomzation
  • Dispersers
  • Extractors
  • Linearized polynomials

Fingerprint

Dive into the research topics of 'Affine dispersers from subspace polynomials'. Together they form a unique fingerprint.

Cite this