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
Skeuomorphic Wayland Compositor
0Hacker News New
Quantum communication: a discrimination approach
0arXiv math.IT
Impact of metric characteristics of the matrix graph on the convergence of the conjugate gradient method
0arXiv cs.NA
Symplectic Hamiltonian Direct Discontinuous Galerkin Method for Wave Propagation
0arXiv cs.NA
Show HN: Document parsing 5B tokens on a single CPU thread
0Hacker News Show
Show HN: In-material physical solver for stiff 64-spin Ising problems (0.27ms)
0Hacker News Show