Affine dispersers from subspace polynomials

Eli Ben-Sasson, Swastik Kopparty

Research output: Contribution to journalArticle

20 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)

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

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

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

Cite this