Polynomial-time algorithms for the Polynomial Freiman-Ruzsa theorem and equivalent formulations over F_2^n, based on an optimized quadratic Goldreich-Levin procedure.
Title resolution pending
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 5roles
background 1polarities
background 1representative citing papers
Moonflowers are introduced as set families with per-set unique elements, yielding near-optimal extremal bounds that enable logarithmic code sparsification with a matching lower bound.
A general framework and query-efficient algorithms for learning structured quantum unitaries based on Pauli spectrum support on small subgroups or sparsity, unifying prior results for multiple circuit classes.
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
Derives Õ(d β² A² / ε⁴) oracle complexity for AIS estimating normalizing constant Z to relative error ε and introduces reverse diffusion sampler for geometric paths with large action.
citing papers explorer
-
An algorithmic Polynomial Freiman-Ruzsa theorem
Polynomial-time algorithms for the Polynomial Freiman-Ruzsa theorem and equivalent formulations over F_2^n, based on an optimized quadratic Goldreich-Levin procedure.
-
Moonflowers and efficient code sparsification
Moonflowers are introduced as set families with per-set unique elements, yielding near-optimal extremal bounds that enable logarithmic code sparsification with a matching lower bound.
-
Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity
A general framework and query-efficient algorithms for learning structured quantum unitaries based on Pauli spectrum support on small subgroups or sparsity, unifying prior results for multiple circuit classes.
-
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
-
Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond
Derives Õ(d β² A² / ε⁴) oracle complexity for AIS estimating normalizing constant Z to relative error ε and introduces reverse diffusion sampler for geometric paths with large action.