We give a $n^{O(\ell)}$-time algorithm for solving semirandom planted instances of a $k$-ary Boolean constraint satisfaction problem (CSP) with $m \gtrsim \left(\frac{n}{\ell}\right)^{k/2} \ell \, \mathrm{polylog}(n)$ constraints, for any choice of the runtime parameter $\ell$. Up to $\mathrm{polylog}(n)$ factors, this matches the known runtime vs.\ number of constraints trade-off for refuting semirandom CSPs, as well as the trade-off for solving fully random planted CSPs. Prior work on designing algorithms for semirandom CSPs follows a high-level blueprint of decomposing the constraint hypergraph $\mathcal{H}$ of the instance into pieces, each with an explicit pseudorandom property that allows the standard algorithm for random CSPs to succeed on every piece. We depart considerably from this framework and instead implicitly \emph{learn} such a decomposition, without appealing directly to explicit properties such as expansion. More generally, we construct such a learning algorithm from the assumption that semirandom $k$-XOR has Sum-of-Squares certificates of refutation. This yields the broader implication that any Sum-of-Squares refutation algorithm for semirandom $k$-XOR gives a corresponding algorithm for solving semirandom planted CSPs, and instantiating this reduction with known Sum-of-Squares algorithms for refuting semirandom $k$-XOR gives our main algorithm. To the best of our knowledge, this is the first reduction from search to refutation for (semi)random CSPs.
Ainesh Bakshi, Arpon Basu, Pravesh Kothari, Anqi Li
原文摘要
We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level $k$ Kikuchi graph of any graph $G$ with $m$ edges is at most $m+k$. This confirms four recent conjectures of Apte, Parekh, and Sud. As applications, we obtain that tensor products of one and two qubit product states achieve an approximation ratio of $5/8$ for Quantum Max Cut and $5/7$ for the XY Hamiltonian. Moreover, combining our bounds with the algorithms analyzed by Apte, Parekh, and Sud, yields efficient algorithms achieving an approximation ratio of $0.614$ for Quantum Max Cut and $0.674$ for the XY Hamiltonian. Finally, we also make modest progress on Brouwer's conjecture and improve Lew's bound on the sum of the top-$k$ eigenvalues of a Graph Laplacian.
Arpon Basu, Pravesh K. Kothari, Raghu Meka, Stefan Tudose
原文摘要
We prove that for every Cayley graph $\mathcal{G}$ over any finite abelian group $G$, there is a weighted Cayley graph with $O(\log |G|)$ generators that is a spectral sparsifier for $\mathcal{G}$. This bound is optimal. Applying our bound to the group $G = \mathbb{F}_2^n$, yields, as a corollary, $O(n/\varepsilon^2)$-sized code sparsifiers for $\mathbb{F}_2$-linear codes, improving on the work of Khanna, Putterman and Sudan (SODA'24) who obtained a similar result with an additional $\mathrm{polylog}(n)$ loss. Our proof is strongly inspired by a recent work of Reis and Rothvoss for the construction of $\ell_1$-sparsifiers. Following their work, the abelian Cayley sparsification problem can be reduced to establishing a lower bound for the volume of a certain natural convex body. This volume bound follows from a short, elementary argument that relies on character symmetry.