Affine extractors over prime fields
An affine extractor is a map from the \(n\)-dimensional vector space over a finite field to the field that is balanced on every affine subspace of sufficiently large dimension. Affine extractors have been studied by \textit{A.~Gabizon} and \textit{R.~Raz} [Combinatorica 28, No. 4, 415--440 (2008; Zbl 1174.05117)] for large fields and by \textit{J.~Bourgain} [Geom.\ Funct.\ Anal. 17, No. 1, 33--57 (2007; Zbl 1115.68108)] for the binary field. Here the author constructs affine extractors for any field of prime order. His construction is reminiscent to Bourgain's but different. The proof is based on bounds on certain exponential sums.
- Deterministic extractors for affine sources over large fields
- ESTIMATES FOR THE NUMBER OF SUMS AND PRODUCTS AND FOR EXPONENTIAL SUMS IN FIELDS OF PRIME ORDER
- Multilinear exponential sums in prime fields under optimal entropy condition on the sources
- On the construction of affine extractors
- Three XOR-lemmas -- an exposition
- Gate elimination: circuit size lower bounds and \#SAT upper bounds
- Improving the Hadamard extractor
- How to extract useful randomness from unreliable sources
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Satisfiability algorithms and lower bounds for Boolean formulas over finite bases
- An introduction to randomness extractors
- Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Zero-fixing extractors for sub-logarithmic entropy
- From affine to two-source extractors via approximate duality
- Affine extractors over large fields with exponential error
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- Affine-evasive sets modulo a prime
- Secret sharing with binary shares
- Extractors and lower bounds for locally samplable sources
- scientific article; zbMATH DE number 7706045 (Why is no real title available?)
- Improving \(3N\) circuit complexity lower bounds
- Explicit directional affine extractors and improved hardness for linear branching programs
- Two-source and affine non-malleable extractors for small entropy
- Extractors for polynomial sources over \(\mathbb{F}_2\)
- Bit-fixing extractors for almost-logarithmic entropy
- On the construction of affine extractors
This page was built for publication: Affine extractors over prime fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653998)
