Quadratic Extractors
Abstract
A quadratic source is a random variable X∼𝔽2n generated by applying n quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly k=n−√(log n). In this paper, we give an explicit construction for min-entropy k=polylog(n). Even for the special case of $2$-local sources, where each bit of X depends on two hidden uniform bits, achieving an entropy requirement below k=√n was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to our most powerful general-purpose seedless extractor, known as a sumset extractor. Our new extractor bypasses this barrier, providing the first explicit construction to go beyond sumset extraction.
Related
- Cyclotomic Prime Extractors
- Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds
- Iterated Monodromy Groups of Quadratic Polynomials, I
- Quadratic differentials and random walks on the dual graph of a pants decomposition
- Ideal class groups of certain real quadratic number fields and factorizations of values of certain quadratic polynomials
BibTeX
@misc{chandrasekaran2026quadratic,
title = {{Quadratic Extractors}},
author = {Gautam Chandrasekaran and Jesse Goodman and David Zuckerman},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07266},
eprint = {2611.07266},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07266},
}
RIS
TY - UNPB
TI - Quadratic Extractors
AU - Gautam Chandrasekaran
AU - Jesse Goodman
AU - David Zuckerman
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07266
UR - https://arxiv.org/abs/2611.07266
AB - A quadratic source is a random variable X∼𝔽_2^n generated by applying n quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly k=n−√(log n). In this paper, we give an explicit construction for min-entropy k=polylog(n). Even for the special case of $2$-local sources, where each bit of X depends on two hidden uniform bits, achieving an entropy requirement below k=√n was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to our most powerful general-purpose seedless extractor, known as a sumset extractor. Our new extractor bypasses this barrier, providing the first explicit construction to go beyond sumset extraction.
ER -