Quadratic extractors achieve polylog entropy for quadratic sources
Original title: Quadratic Extractors
New explicit construction works for min-entropy k=polylog(n) on quadratic sources, bypassing the sumset extractor barrier for 2-local sources.
A quadratic source is generated by applying n quadratics to a hidden uniform string in F_2^n. Previous explicit extractors required min-entropy roughly k=n-√(log n). The new construction succeeds at k=polylog(n). For 2-local sources, where each output bit depends on two hidden bits, it achieves entropy below √n, which was previously an open problem because such sources cannot be reduced to sumset extractors. The extractor bypasses this barrier with a construction that goes beyond sumset extraction.
- First explicit extractor for quadratic sources at polylog(n) entropy
- Works for general quadratic sources and 2-local sources
- Avoids black-box reduction to sumset extractors
- Explicit construction for k=polylog(n)
- Improves on previous min-entropy threshold
From the original article
1 min read at arxiv.orgA 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)$.
By Gautam Chandrasekaran · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.