The Kikuchi Hierarchy is Sharp for $k$XOR

• URL: http://arxiv.org/abs/2607.29672v1
• Date: Fri, 31 Jul 2026 17:54:11 GMT
• Title: The Kikuchi Hierarchy is Sharp for $k$XOR
• Abstract summary: We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity $kge3$.<n>We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates.
• Score: 46.26532142699448
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Planted noisy $k$XOR and the strong refutation of random $k$XOR are governed by a conjectured trade-off between signal strength and time: Level $\ell$ of the Kikuchi hierarchy should achieve the smooth curve \begin{equation*} m\ \gtrsim\ ρ^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} where $ρ$ is the bias of the planted signal or, for refutation, the target advantage. However, every spectral analysis of sparse $k$XOR to date loses polylogarithmic factors against this curve, a loss that enters the exponent of the running time. We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity $k\ge3$. At the scale above, our algorithms achieve strong detection, weak recovery, and strong refutation; an additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree $O_k(\ell)$. We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates. Finally, we give a quantum algorithm that achieves a quartic speedup over the classical spectral algorithms for detection and weak recovery. The proofs rest on two key ingredients: a normalization of the sparse Kikuchi matrix, and a sharp count of the closed walks in its trace expansion. We use a closely related trace-walk count to prove Feige's 2008 hypergraph Moore bound conjecture in a companion paper.

Related papers

• An Argmax Principle for Sum-of-Squares Relaxations on the Sphere [42.540924632302925]
  We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere.<n>Our guiding principle is that its maximizers are rounding candidates.
  arXiv  Detail & Related papers  (2026-08-03T17:58:00Z)
• A phase transition in the exactness of the NPA hierarchy at the critical doubly-tilted CHSH functional [0.0]
  We prove the exact quantum maximum of the doubly-tilted CHSH functional $B_=langle A_0rangle+l B_0rangle+mathrmCHSH$.<n>For all $,ge 1$ and every level the hierarchy is exact, via three explicit rational certificates realizing an affine identity.<n>On the subcritical side we certify the first four levels in exact arithmetic.
  arXiv  Detail & Related papers  (2026-07-15T12:34:25Z)
• Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization [0.0]
  We consider the recovery of a pair of sparse vectors from a limited number of nonlinear observations of their superposition.<n>We propose a regularization-based framework combining a Huberized data fidelity with generalized folded-concave penalties.<n>We derive estimation error bounds of order $sqrtslog(n)/m$ that hold at emphevery localized stationary point.
  arXiv  Detail & Related papers  (2026-07-12T07:29:39Z)
• Coupled Tensor-Matrix Recovery via Proximal Alternating Linearized Minimization, with an Application to Workforce Skill and Small-Business Health Estimation [0.0]
  We study recovery of a lowrank tensor $mathcalT$ and a low-rank matrix $M$ from noisy observations.<n>For the matrix only problem, we state a proven sampling-complexity result for a sequential sub-case.<n>For the fully joint, alternately-estimated case, we state a conjecture.
  arXiv  Detail & Related papers  (2026-07-11T07:06:08Z)
• Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
  We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element.<n>Our main result bounds the regret by $widetildeObig(sqrtT, d_*(),log|X|big)$, where $d_*()$ is a widely-adopted notion of effective dimension.
  arXiv  Detail & Related papers  (2026-05-26T06:10:24Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• The Marginal Problem for Density Operators [0.30079490585515334]
  We study when local reduced density operators can be assembled into a global quantum state with a prescribed Markov structure.<n>We prove that this obstruction is captured exactly by a trace condition.<n>Three-qubit Pauli examples show that the quantum obstructions are real.
  arXiv  Detail & Related papers  (2026-05-19T07:06:54Z)
• When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias [15.113649527486276]
  We show that benign overfitting fails at the linear rate.<n>We show that while this localization mechanism should persist in the presence of signals, the exact signal-noise decomposition remains an open problem.
  arXiv  Detail & Related papers  (2026-05-07T14:14:09Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities [51.320599504997745]
  Predictions from statistical physics postulate that recovery of the communities in Block Model (SBM) is possible in time above, and only above, the KestenStigum (KS) threshold.<n>Chin et al.(2025) recently prove that, in a sparse regime, community recovery in time is possible below the KS threshold by counting nonbacktracking paths.
  arXiv  Detail & Related papers  (2025-09-19T09:53:56Z)
• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$.<n>We derive an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains.<n>We then present a novel two-stage clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-02T05:10:40Z)
• Convergence Rate Analysis of LION [54.28350823319057]
  LION converges iterations of $cal(sqrtdK-)$ measured by gradient Karush-Kuhn-T (sqrtdK-)$. We show that LION can achieve lower loss and higher performance compared to standard SGD.
  arXiv  Detail & Related papers  (2024-11-12T11:30:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.