Affine extractors over large fields with exponential error

DOI10.1007/S00037-015-0108-5zbMATH Open1419.11132arXiv1401.6189OpenAlexW1517838246MaRDI QIDQ347127FDOQ347127

Authors: Jean Bourgain, Zeev Dvir, Ethan Leeman 

Publication date: 30 November 2016

Published in: Computational Complexity (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1401.6189

Recommendations

• On the construction of affine extractors
• Affine extractors over prime fields
• Deterministic extractors for affine sources over large fields
• Affine dispersers from subspace polynomials
• Extractors and rank extractors for polynomial sources

zbMATH Keywords

derandomizationfinite fieldsexplicit constructions

Mathematics Subject Classification ID

Randomized algorithms (68W20) Exponential sums (11T23)

Cites Work

• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• La conjecture de Weil. I
• Title not available (Why is that?)
• Ramanujan graphs
• Minimum distance bounds for cyclic codes and Deligne's theorem
• Affine extractors over prime fields
• On the construction of affine extractors
• Extractors for varieties
• Deterministic extractors for affine sources over large fields
• 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
• On exponential sums in finite fields
• Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
• Extractors and rank extractors for polynomial sources

Cited In (7)

• Deterministic extractors for affine sources over large fields
• Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
• How to extract useful randomness from unreliable sources
• Title not available (Why is that?)
• Analogues of the Balog-Wooley decomposition for subsets of finite fields and character sums with convolutions
• Affine extractors over prime fields
• On the construction of affine extractors

This page was built for publication: Affine extractors over large fields with exponential error

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q347127)