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
Karpathy Skills: One File That Makes Your AI Coding Agent Write Better Code
0dev.to OpenSource
T3 Code: Control All Your AI Coding Agents From Your Phone
0dev.to OpenSource
OpenMontage: Turn Your AI Coding Assistant Into a Full Video Production Studio
0dev.to OpenSource
Code animation tool: five ways to animate code on screen for a video or a Short
0dev.to Programming
Why FreePi runs on the Pi harness (and what the new Harness Leaderboard shows)
0dev.to Programming
Skeuomorphic Wayland Compositor
0Hacker News New