pith. sign in

arxiv: 2606.08597 · v1 · pith:TDSGQNZOnew · submitted 2026-06-07 · 💻 cs.DS · math.CO

Kikuchi Graphs of Random Hypergraphs are Approximately Johnson

Pravesh K. Kothari This is my paper

Pith reviewed 2026-06-27 17:57 UTC · model grok-4.3

classification 💻 cs.DS math.CO
keywords Kikuchi graphsspectral approximationrandom hypergraphssum-of-squaresMax 2r-XORJohnson graphsmatrix Bernstein
0
0 comments X

The pith

Kikuchi graphs of random 2r-uniform hypergraphs spectrally approximate the complete hypergraph version at rates sharp up to a log factor.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that level-ℓ Kikuchi graphs built from random 2r-uniform hypergraphs are spectrally close to the Kikuchi graph of the full complete 2r-uniform hypergraph. The closeness holds with a number of hyperedges that is sharp up to a logarithmic factor when r ≤ ℓ ≤ n/2. The argument introduces a band-locality property that lets matrix Bernstein be applied to blocks of Johnson eigenspaces. A reader cares because the result immediately shows that the natural degree-2ℓ sum-of-squares relaxation for Max 2r-XOR is integral on planted noisy instances drawn from such random hypergraphs.

Core claim

Level-ℓ Kikuchi graphs of random 2r-uniform hypergraphs spectrally approximate the Kikuchi graph of the complete 2r-uniform hypergraph at a sampling rate that is sharp up to a logarithmic factor, in the regime r≤ℓ≤n/2. The proof relies on a new band-locality property for arbitrary Kikuchi graphs and applies the matrix Bernstein inequality to an appropriate collection of blocks of Johnson eigenspaces. As an application, the natural degree-2ℓ sum-of-squares relaxation for the Max 2r-XOR problem is integral when the input is a planted noisy 2r-XOR instance on a random hypergraph with ≳ n · (n/ℓ)^{r-1} log n hyperedges.

What carries the argument

The band-locality property for arbitrary Kikuchi graphs, which permits applying matrix Bernstein to blocks of Johnson eigenspaces.

If this is right

  • The degree-2ℓ sum-of-squares relaxation for Max 2r-XOR is integral on planted noisy instances with at least roughly n·(n/ℓ)^{r-1} log n hyperedges.
  • Spectral approximation transfers eigenvalue and eigenspace properties from the complete hypergraph to the random case.
  • The approximation quality is tight up to logs, so fewer hyperedges would violate the spectral closeness.
  • The result applies throughout the regime r≤ℓ≤n/2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same blocking technique could be tested on Kikuchi graphs arising from other random combinatorial objects.
  • Integrality of the relaxation may extend to related planted problems whose Kikuchi graphs obey band-locality.
  • Tighter analysis without the log factor might be possible if the band-locality constants can be improved.

Load-bearing premise

The band-locality property holds for arbitrary Kikuchi graphs and thereby allows the matrix Bernstein inequality to be applied to the chosen blocks of Johnson eigenspaces.

What would settle it

A numerical computation of the operator-norm difference between the adjacency matrix of a level-ℓ Kikuchi graph on a random 2r-uniform hypergraph and the complete case, for parameters inside r≤ℓ≤n/2, that exceeds the claimed bound by more than the logarithmic factor.

read the original abstract

We prove that level-$\ell$ Kikuchi graphs of random $2r$-uniform hypergraphs spectrally approximate the Kikuchi graph of the complete $2r$-uniform hypergraph at a sampling rate that is sharp up to a logarithmic factor, in the regime $r\leq \ell \leq n/2$. Our proof is based on the matrix Bernstein inequality, but, unlike prior works, we apply it to an appropriate collection of blocks of Johnson eigenspaces. Our analysis relies on a new, simple band-locality property for arbitrary Kikuchi graphs. As an application, we prove that the natural degree-$2\ell$ sum-of-squares relaxation for the Max $2r$-XOR problem is ``integral'' when the input is a planted noisy $2r$-XOR instance on a random hypergraph with $\gtrsim n \cdot (n/\ell)^{r-1} \log n$ hyperedges.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proves that level-ℓ Kikuchi graphs of random 2r-uniform hypergraphs spectrally approximate the Kikuchi graph of the complete 2r-uniform hypergraph at a sampling rate sharp up to a logarithmic factor, for r ≤ ℓ ≤ n/2. The proof applies the matrix Bernstein inequality to blocks of Johnson eigenspaces, relying on a new band-locality property of arbitrary Kikuchi graphs. As an application, it shows that the degree-2ℓ sum-of-squares relaxation for Max 2r-XOR is integral on planted noisy instances with ≳ n · (n/ℓ)^{r-1} log n hyperedges.

Significance. If the approximation holds with the stated sharpness, the result supplies a precise spectral tool for analyzing SoS hierarchies on random hypergraphs, directly yielding integrality for a natural relaxation of Max 2r-XOR. The band-locality property is presented as a simple, general observation that enables the block-wise concentration argument; if verified, it strengthens the technical toolkit for spectral methods in hypergraph CSPs and may apply beyond the current setting.

major comments (1)
  1. [Abstract] Abstract (proof technique paragraph): the band-locality property is invoked to obtain the variance bounds needed for matrix Bernstein on Johnson eigenspace blocks; the manuscript must state the property explicitly (including the precise band width and the resulting operator-norm or Frobenius variance bound) and prove it for arbitrary Kikuchi graphs so that the claimed sharpness up to log n can be checked.
minor comments (2)
  1. [Theorem 1.1 (presumed)] The regime r ≤ ℓ ≤ n/2 is stated cleanly, but the dependence of the hidden constants on r and ℓ should be made explicit in the main theorem statement to clarify the range where the log-factor gap is meaningful.
  2. [Section 2] Notation for the Kikuchi graph adjacency operator and the Johnson eigenspaces should be introduced with a short table or diagram in the preliminaries to aid readers unfamiliar with the construction.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive recommendation of minor revision and the helpful comment on clarifying the band-locality property. We address the point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (proof technique paragraph): the band-locality property is invoked to obtain the variance bounds needed for matrix Bernstein on Johnson eigenspace blocks; the manuscript must state the property explicitly (including the precise band width and the resulting operator-norm or Frobenius variance bound) and prove it for arbitrary Kikuchi graphs so that the claimed sharpness up to log n can be checked.

    Authors: We agree that the abstract's proof-technique sentence would benefit from an explicit (if brief) statement of the band-locality property, including band width and the variance bound that feeds into matrix Bernstein, so that the log n sharpness can be verified at a glance. The full manuscript already defines the property for arbitrary Kikuchi graphs and proves the required variance bound in Section 3; the random-hypergraph analysis then applies it to the Johnson blocks. To satisfy the request we will revise the abstract by expanding the relevant sentence to read: "Our analysis relies on a new band-locality property of arbitrary Kikuchi graphs (band width 2, yielding Frobenius variance O((n/ℓ)^{r-1} log n) on the relevant Johnson blocks) that enables the matrix Bernstein argument." This is a minor textual change that does not alter any theorems or proofs. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation proceeds from the matrix Bernstein inequality applied to blocks of Johnson eigenspaces, enabled by a newly stated band-locality property that holds for arbitrary Kikuchi graphs. This is an independent analytic step whose variance bounds are derived from the property rather than from any fitted parameter, self-cited prediction, or definitional equivalence. The subsequent SoS integrality claim follows directly once the spectral approximation is established. No load-bearing self-citation chain, ansatz smuggling, or renaming of known results appears in the abstract or proof sketch; the argument is therefore self-contained against standard matrix-concentration benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities are stated.

pith-pipeline@v0.9.1-grok · 5684 in / 1155 out tokens · 18371 ms · 2026-06-27T17:57:03.046459+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 3 linked inside Pith

  1. [1]

    Conjectured Bounds for 2-Local Hamiltonians via Token Graphs.CoRR, abs/2506.03441,

    [APS25] Anuj Apte, Ojas Parekh, and James Sud. Conjectured Bounds for 2-Local Hamiltonians via Token Graphs.CoRR, abs/2506.03441,

    Pith/arXiv arXiv

  2. [2]

    Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut.CoRR, abs/2605.14994,

    [BBKL26] Ainesh Bakshi, Arpon Basu, Pravesh Kothari, and Anqi Li. Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut.CoRR, abs/2605.14994,

    Pith/arXiv arXiv

  3. [3]

    Kothari, and Andrew D

    [BHKL25] Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari, and Andrew D. Lin. Improved Lower Bounds for all Odd-Query Locally Decodable Codes. InProceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, pages 1262–1285. IEEE Computer Society,

    2025

  4. [4]

    [BHLM25] Arpon Basu, Jun-Ting Hsieh, Andrew D

    Also available as arXiv:2411.14361,https: //arxiv.org/abs/2411.14361. [BHLM25] Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin, and Peter Manohar. Solving Random Planted CSPs below then k/2 Threshold.CoRR, abs/2507.10833,

    arXiv

  5. [5]

    Kothari, Yang P

    [BKLM26] Arpon Basu, Pravesh K. Kothari, Yang P. Liu, and Raghu Meka. Sparsifying Sums of Positive Semidefinite Matrices. InProceedings of the 2026 ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, pages 6042–6064. SIAM,

    2026

  6. [6]

    [CGL07] Amin Coja-Oghlan, Andreas Goerdt, and Andr´ e Lanka

    arXiv:2508.08169, https://arxiv.org/abs/2508.08169. [CGL07] Amin Coja-Oghlan, Andreas Goerdt, and Andr´ e Lanka. Strong refutation heuristics for randomk-SAT.Combinatorics, Probability & Computing, 16(1):5,

    arXiv

  7. [7]

    [DFM25] Cristina Dalf´ o, Miquel `Angel Fiol, and Arnau Messegu´ e

    Also available as arXiv:2012.00808,https://arxiv.org/abs/2012.00808. [DFM25] Cristina Dalf´ o, Miquel `Angel Fiol, and Arnau Messegu´ e. Some Bounds on the Lapla- cian Eigenvalues of Token Graphs.Discrete Mathematics, 348(4):114382,

    arXiv 2012

  8. [8]

    [FFH+12] Ruy Fabila-Monroy, David Flores-Pe˜ naloza, Clemens Huemer, Ferran Hurtado, Jorge Urrutia, and David R

    Also available as arXiv:2309.09041,https://arxiv.org/abs/2309.09041. [FFH+12] Ruy Fabila-Monroy, David Flores-Pe˜ naloza, Clemens Huemer, Ferran Hurtado, Jorge Urrutia, and David R. Wood. Token Graphs.Graphs and Combinatorics, 28(3):365– 380,

    arXiv

  9. [9]

    Kothari, and Peter Manohar

    [GHKM23] Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, and Peter Manohar. Efficient algorithms for semirandom planted csps at the refutation threshold. In64th 13 IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 307–327. IEEE,

    2023

  10. [10]

    Efficient Recognition of Random Unsatisfi- ablek-SAT Instances by Spectral Methods

    [GK01] Andreas Goerdt and Michael Krivelevich. Efficient Recognition of Random Unsatisfi- ablek-SAT Instances by Spectral Methods. InProceedings of the 18th Annual Sympo- sium on Theoretical Aspects of Computer Science, STACS 2001, volume 2010 ofLecture Notes in Computer Science, pages 294–304. Springer,

    2001

  11. [11]

    Kothari, and Peter Manohar

    [GKM22] Venkatesan Guruswami, Pravesh K. Kothari, and Peter Manohar. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. InSTOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 678–689. ACM,

    2022

  12. [12]

    [HKM23] Jun-Ting Hsieh, Pravesh K

    arXiv:1907.12724. [HKM23] Jun-Ting Hsieh, Pravesh K. Kothari, and Sidhanth Mohanty. A simple and sharper proof of the hypergraph Moore bound. InProceedings of the 2023 ACM-SIAM Sympo- sium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 2324–2344. SIAM,

    arXiv 1907

  13. [13]

    Kothari, Sidhanth Mohanty, David Munh´ a Correia, and Benny Sudakov

    [HKM+24] Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty, David Munh´ a Correia, and Benny Sudakov. Small Even Covers, Locally Decodable Codes and Restricted Sub- graphs of Edge-Colored Kikuchi Graphs.CoRR, abs/2401.11590,

    arXiv

  14. [14]

    Lee, Sidhanth Mohanty, Aaron Putterman, and Rachel Yun Zhang

    [HLM+26] Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty, Aaron Putterman, and Rachel Yun Zhang. Sparsifying Cayley Graphs on Every Group. InProceedings of the 2026 ACM- SIAM Symposium on Discrete Algorithms, SODA 2026, pages 6029–6041. SIAM,

    2026

  15. [15]

    [KM24a] Pravesh K

    arXiv:2508.08078,https://arxiv.org/abs/2508.08078. [KM24a] Pravesh K. Kothari and Peter Manohar. An Exponential Lower Bound for Linear 3- Query Locally Correctable Codes. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 776–787. ACM,

    arXiv 2024

  16. [16]

    [KM24b] Pravesh K

    Also available as arXiv:2311.00558,https://arxiv.org/abs/2311.00558. [KM24b] Pravesh K. Kothari and Peter Manohar. Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. InProceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, pages 1802–1845. IEEE Computer Society,

    arXiv 2024

  17. [17]

    Also available as arXiv:2404.06513,https://arxiv.org/abs/2404. 06513. [Lew24] Alan Lew. Garland’s Method for Token Graphs.Linear Algebra and its Applications, 700:50–60,

    arXiv

  18. [18]

    Also available as arXiv:2305.02406,https://arxiv.org/abs/2305. 02406. [Lew26] Alan Lew. An Approximate Version of Brouwer’s Laplacian Conjecture.CoRR, abs/2601.17575,

    arXiv

  19. [19]

    Near Optimal Algorithms for Noisyk-XOR under Low-Degree Heuristic

    14 [Mao26] Songtao Mao. Near Optimal Algorithms for Noisyk-XOR under Low-Degree Heuristic. CoRR, abs/2604.10457,

    Pith/arXiv arXiv

  20. [20]

    Reyes, Cristina Dalf´ o, Miquel `Angel Fiol, and Arnau Messegu´ e

    [RDFM23] M´ onica A. Reyes, Cristina Dalf´ o, Miquel `Angel Fiol, and Arnau Messegu´ e. On the Spectra of Token Graphs of Cycles and Other Graphs.CoRR, abs/2309.07089,

    arXiv

  21. [21]

    Spielman and Nikhil Srivastava

    [SS11] Daniel A. Spielman and Nikhil Srivastava. Graph Sparsification by Effective Resis- tances.SIAM Journal on Computing, 40(6):1913–1926,

    1913

  22. [22]

    Wein, Ahmed El Alaoui, and Cristopher Moore

    [WAM19] Alexander S. Wein, Ahmed El Alaoui, and Cristopher Moore. The Kikuchi Hierarchy and Tensor PCA. In David Zuckerman, editor,60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1446–1468. IEEE Computer Society,

    2019

  23. [23]

    A Stronger Bound for Linear 3-LCC

    [Yan24] Tal Yankovitz. A Stronger Bound for Linear 3-LCC. InProceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, pages 1786–

    2024

  24. [24]

    Also available as ECCC TR24-036,https:// eccc.weizmann.ac.il/report/2024/036/. 15

    2024