Open Source
Quadratic Extractors
arXiv cs.CR0 views
arXiv:2611.07266v1 Announce Type: cross Abstract: 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 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.
Source:https://arxiv.org/abs/2611.07266PreviousFedReason: Large Language Models as Weight-Space Meta-Aggregators for Heterogeneous Federated LearningNextExact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
Related posts
systemd gains support for Rust language but imposes strict rules
0dev.to Linux
One outage email per account, listing its affected services
0dev.to DevOps
Show HN: Good First Token – Spend your spare tokens on open source
0Hacker News Show
How video game remakes tap the power of nostalgia
0dev.to OpenSource
I submitted a free skill pack to 6 awesome lists — 1 merged, 3 ignored, 1 closed for having 1 star
0dev.to OpenSource
🚀 Introducing Karasu Enhancer — A Browser Extension for a Better Karasu.live Experience
0dev.to AI