Affine extractors over large fields with exponential error

Jean Bourgain; Zeev Dvir; Ethan Leeman

doi:10.1007/s00037-015-0108-5

Affine extractors over large fields with exponential error

Jean Bourgain, Zeev Dvir, Ethan Leeman

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.

Original language	English (US)
Pages (from-to)	921-931
Number of pages	11
Journal	Computational Complexity
Volume	25
Issue number	4
DOIs	https://doi.org/10.1007/s00037-015-0108-5
State	Published - Dec 1 2016

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Mathematics
Computational Mathematics
Computational Theory and Mathematics

Keywords

Explicit constructions
derandomization
finite fields

Access to Document

10.1007/s00037-015-0108-5

Cite this

@article{dc8dd0645a2f4a26903607aedacd0fc5,

title = "Affine extractors over large fields with exponential error",

abstract = "We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.",

keywords = "Explicit constructions, derandomization, finite fields",

author = "Jean Bourgain and Zeev Dvir and Ethan Leeman",

note = "Publisher Copyright: {\textcopyright} 2015, Springer Basel.",

year = "2016",

month = dec,

day = "1",

doi = "10.1007/s00037-015-0108-5",

language = "English (US)",

volume = "25",

pages = "921--931",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "4",

}

TY - JOUR

T1 - Affine extractors over large fields with exponential error

AU - Bourgain, Jean

AU - Dvir, Zeev

AU - Leeman, Ethan

PY - 2016/12/1

Y1 - 2016/12/1

N2 - We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.

AB - We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.

KW - Explicit constructions

KW - derandomization

KW - finite fields

UR - https://www.scopus.com/pages/publications/84940559463

UR - https://www.scopus.com/inward/citedby.url?scp=84940559463&partnerID=8YFLogxK

U2 - 10.1007/s00037-015-0108-5

DO - 10.1007/s00037-015-0108-5

M3 - Article

AN - SCOPUS:84940559463

SN - 1016-3328

VL - 25

SP - 921

EP - 931

JO - Computational Complexity

JF - Computational Complexity

IS - 4

ER -

Affine extractors over large fields with exponential error

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this