{"id":"arxiv/2611.07266","url":"https://arxiv.org/abs/2611.07266","tags":["cs.CC","cs.CR","math.CO"],"score":0,"title":"Quadratic Extractors","domain":"cs.CC","source":"arxiv","authors":["Gautam Chandrasekaran","Jesse Goodman","David Zuckerman"],"reviews":0,"subject":"cs.CC","summary":"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, where each bit of $X$ depends on two hidden uniform bits, achieving an entropy requirement below $k=\\sqrt{n}$ was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-05","reactions":{}}