ECCC - Gautam Chandrasekaran
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > GAUTAM CHANDRASEKARAN:
All reports by Author Gautam Chandrasekaran:

TR26-303 | 5th November 2026
Gautam Chandrasekaran, Jesse Goodman, David Zuckerman

Quadratic Extractors

A quadratic source is a random variable $X\sim\mathbb{F}_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-\sqrt{\log n}$. In this paper, we give an explicit construction for min-entropy $k=\mathrm{polylog}(n)$. Even for the special case of $2$-local sources, ... more >>>




ISSN 1433-8092 | Imprint