Pith. sign in

REVIEW 4 minor 224 references

The expected operator norm of the SYK Hamiltonian is asymptotically √(2n)/k for super-constant k up to o(√n).

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-30 10:53 UTC pith:XRLWPYKV

load-bearing objection Clean resolution of the SYK spectral edge via a new twisted-boson moment match; the proof chain is complete and the constant is sharp for growing k.

arxiv 2607.27185 v1 pith:XRLWPYKV submitted 2026-07-29 quant-ph math.PR

Sharp Bounds on Ground State Energy of the SYK Model

Arpon Basu , Pravesh K. Kothari , Siddhant Midha This is my paper
classification quant-ph math.PR MSC 81Q1060B2005E3015B52 PACS 05.30.-d03.65.Fd05.45.Mt
keywords SYK modeloperator normground-state energytwisted bosonsJohnson schemesparse SYKtrace momentsMajorana fermions
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The Sachdev–Ye–Kitaev Hamiltonian is a random quantum model built from k-body interactions among n Majorana modes. Physicists had long predicted that its typical largest eigenvalue should scale as √(2n)/k once k grows (slowly) with n, but existing rigorous bounds left a large multiplicative gap. This paper proves the prediction: the expected operator norm equals (1−o(1))·√(2n)/k whenever k is super-constant and o(√n). The same asymptotic holds for sparse random versions of the model. As a direct consequence, an existing dissipative quantum algorithm is shown to approximate the ground-state energy up to a constant factor throughout this range. The argument works by matching every expected moment of the random Hamiltonian to a vacuum expectation in an explicit deterministic “twisted boson” operator whose spectrum is controlled by a classical matrix from the Johnson association scheme.

Core claim

For even integers n≥k≥2 with k²/n<1/16, the expected operator norm of the SYK Hamiltonian satisfies √(2n)/k·(1−O(max{k^{−1/2},k⁴/n²}))≤E∥H_SYK∥_op≤√(2n)/k+O(1). In particular, when ω(1)≤k≤o(√n) one obtains the sharp asymptotic E∥H_SYK∥_op=(1−o(1))·√(2n)/k; the same edge holds for sparse random hypergraphs with sufficiently many edges.

What carries the argument

An explicit deterministic operator x=a+a* built from twisted bosonic modes on hyperedges, engineered so that the vacuum quadratic form ⟨f₀,x^{2ℓ}f₀⟩ exactly equals the expected normalized trace moment E tr(H_SYK^{2ℓ}) for every n,k,ℓ. Its spectral edge is then read off from the eigenvalues of the associated sign matrix in the Johnson scheme.

Load-bearing premise

The sign matrix that encodes Majorana commutation must stay spectrally close to a rank-one projector (leakage parameters small), which the paper guarantees only when k²/n is less than 1/16.

What would settle it

Direct numerical estimation of the expected operator norm of dense or sparse SYK matrices for a sequence of even n and growing even k with k²/n bounded below 1/16; the measured ratio E∥H∥·k/√(2n) must approach 1 if the claimed edge is correct.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The dissipative quantum algorithm of Basso–Chen–Dalzell achieves an O(1)-factor approximation to the SYK ground-state energy for all k<√n/4.
  • The same sharp edge holds for sparse random SYK Hamiltonians once the hypergraph has at least roughly 2^{Ck}n log n edges.
  • Sub-Gaussian concentration of the operator norm around its mean follows at once from Lipschitz concentration of the Gaussian disorder.
  • For fixed small k the leading constant √2/k is not claimed to be optimal; the paper recovers only the correct asymptotic once k→∞.

Where Pith is reading between the lines

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

  • The twisted-boson moment matching supplies a general template that may transfer to other random fermionic or mixed-commutator Hamiltonians whose exchange signs admit a low-rank Johnson-like description.
  • Because the upper and lower bounds meet only for growing k, a separate exact-edge analysis (already begun for k=4) remains necessary for each fixed arity.
  • The deterministic leakage condition stated for arbitrary hypergraphs suggests a combinatorial design criterion under which any fixed interaction graph would inherit the same spectral edge.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper proves sharp bounds on the expected operator norm of the SYK Hamiltonian on n Majorana modes with k-body interactions: for even n ≥ k ≥ 2 with k²/n < 1/16 one has √(2n)/k · (1 − O(max{k^{-1/2}, k⁴/n²})) ≤ E∥H_SYK∥_op ≤ √(2n)/k + O(1), hence the asymptotic (1−o(1))√(2n)/k when ω(1) ≤ k ≤ o(√n). The same edge holds for sparse random hypergraphs with m ≥ 2^{Ck} n log n edges. The argument constructs a deterministic twisted-bosonic operator x whose vacuum moments exactly match the annealed trace moments of H_SYK (via Isserlis–Wick and the twisted commutation relations), controls the spectral leakage of the associated sign matrix by Johnson-scheme eigenvalues (dense) or matrix Bernstein (sparse), and transfers a Krylov-space lower bound back to H via a Hermite isometry and hypercontractive decoupling. As a corollary the dissipative algorithm of Basso–Chen–Dalzell achieves an O(1)-multiplicative approximation to the ground-state energy for all k < √n/4.

Significance. The result rigorously confirms long-standing physics predictions (García-García–Jia–Verbaarschot) and answers an explicit question of Feng–Tian–Wei, closing a multiplicative gap of order k between prior upper and lower bounds. The finite-(n,k) moment-matching construction via twisted bosons is a clean, reusable technique that also covers sparse SYK and immediately upgrades the known quantum algorithm to a provable O(1)-approximation. Strengths include fully written proofs, explicit use of classical association-scheme spectra, and transparent scoping of the α < 1/16 regime and the non-sharp constant-k prefactors. The work sits at the intersection of random-matrix theory, quantum many-body physics and quantum algorithms and is of clear interest to all three communities.

minor comments (4)
  1. [Remark 1.2] Remark 1.2(2) correctly notes that the prefactor √2/k is not tight for fixed k (e.g. k=2); a short forward pointer in the introduction to the exact k=2 and recent k=4 results would help non-specialist readers calibrate expectations.
  2. [Definition 4.3] The ordering of hyperedges used to define the twist operators K_i is arbitrary; a one-sentence remark that the final spectrum of x is independent of this choice would remove a possible source of confusion.
  3. [Theorem 5.6] In the sparse lower bound the relative error is k^{-1/4} rather than the denser k^{-1/2}; a brief explanation of where the extra square-root loss appears (hypercontractive degree versus leakage) would improve readability.
  4. [Abstract / §1] A few typographical inconsistencies appear (e.g. “Westudythe”, missing spaces after periods in the abstract and early pages). A careful copy-edit pass is recommended.

Circularity Check

0 steps flagged

No significant circularity: spectral edge is derived from an exact moment identity plus external Johnson-scheme eigenvalues, not fitted or assumed.

full rationale

The central claim E∥H_SYK∥_op ∼ √(2n)/k is obtained by (i) constructing twisted bosonic operators a_S so that the vacuum functional equals annealed SYK moments exactly for every n,k,ℓ (Prop. 4.7 / Lem. 4.6 via Isserlis–Wick and Majorana signs), (ii) controlling the sign-matrix leakage (ρ±,δ) by classical Johnson-scheme eigenvalue formulas (Fact 3.1, Lem. 5.1) or matrix Bernstein (sparse case), and (iii) transferring a Krylov-edge lower bound back to H via Hermite isometry and hypercontractivity (Lem. 4.12–4.18). The q-deformed oscillator picture from the doubly-scaled SYK literature is cited only as heuristic motivation (Sec. 2.2–2.3); the finite-(n,k) argument never assumes the target edge. No parameter is fitted to data and re-predicted; no load-bearing uniqueness theorem is imported from the authors’ prior work; Johnson and Bernstein facts are standard external tools. The derivation is self-contained against its stated hypotheses (α=k²/n<1/16).

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 1 invented entities

The proof rests on standard probabilistic and algebraic facts (Isserlis–Wick, Johnson-scheme spectrum, matrix Bernstein, Gaussian Lipschitz and hypercontractivity) plus the canonical Majorana representation. The only paper-specific construction is the twisted-boson algebra designed so that its vacuum moments equal SYK trace moments; once that identity is proved, the rest is spectral analysis of a known association scheme. No numerical fitting.

axioms (6)
  • standard math Isserlis–Wick theorem for Gaussian moments (Fact 3.4)
    Used to expand E[g_{S1}…g_{S2ℓ}] into pairings / chord diagrams.
  • standard math Eigenvalues and eigenspaces of the Johnson association scheme (Fact 3.1 / Delsarte–Wilson)
    Gives closed-form spectrum of the dense sign matrix E; load-bearing for ρ±, δ, q bounds in §5.1.
  • standard math Matrix Bernstein inequality (Fact 3.2 / Tropp)
    Controls sparse sign-matrix leakage via Lemma 3.3.
  • standard math Gaussian Lipschitz concentration and hypercontractivity for degree-L matrix polynomials (Fact 3.7, Prop. 3.8)
    Transfers Krylov witness on x to a lower bound on E∥H∥_op and yields sub-Gaussian tails.
  • domain assumption Majorana operators admit a unitary irrep on C^{2^{n/2}} with Γ_S Γ_T = ε_{S,T} Γ_T Γ_S and Γ_S² = Id
    Standard fermionic algebra (Bravyi–Kitaev); fixed once and for all at the start of §3.
  • ad hoc to paper Hard regime cutoff α = k²/n < 1/16 (and m ≥ 2^{Ck} n log n in the sparse case)
    Chosen so that leakage series and (q−ρ+)+ stay strictly positive; the constant 1/16 is technical, not fundamental.
invented entities (1)
  • Twisted bosonic operators a_S = K_S b_S and collective x = a + a* independent evidence
    purpose: Provide a deterministic operator whose vacuum moments exactly equal E tr(H_SYK^{2ℓ}) for every n,k,ℓ, reducing the random spectral-edge problem to a Johnson-scheme calculation.
    Constructed in Def. 4.3 and Prop. 4.7; the twist operators K_i encode Majorana signs. Related to mixed-q Gaussians and doubly-scaled SYK transfer matrices, but the finite-(n,k) moment identity and the Hermite embedding for the lower bound are specific to this paper.

pith-pipeline@v1.2.0-daily-grok45 · 47243 in / 3515 out tokens · 62047 ms · 2026-07-30T10:53:45.864871+00:00 · methodology

0 comments
read the original abstract

We study the Sachdev-Ye-Kitaev (SYK) Hamiltonian $H_{\operatorname{SYK}}$ on $n$ Majorana modes with $k$-body interactions, and prove that $\mathbb{E}\|H_{\operatorname{SYK}}\|_{\operatorname{op}} = (1 - o(1))\cdot\sqrt{2n}/k$ for super-constant $k\leq o(\sqrt{n})$, where the expectation is over the disorder variables in the Hamiltonian. This confirms the predictions due to Garcia-Garcia, Jia and Verbaarschot'18 and answers a question posed in Feng, Tian and Wei'19. Our results extend to the sparse SYK Hamiltonian. As a corollary, we obtain that the dissipative quantum algorithm of Basso, Chen and Dalzell'24 provably computes the ground state energy of the SYK Hamiltonian up to an $O(1)$-multiplicative factor for all $k < \sqrt{n}/4$. Our key technical idea is identifying an explicit, deterministic linear operator $\mathsf{x}$ such that a fixed quadratic form of $\mathsf{x}^{2\ell}$ exactly equals the expected trace moments of the SYK Hamiltonian for every $n$ and $k$. This linear operator can be naturally viewed as a \emph{twisted} model of bosons on the space of hyperedges of a hypergraph. The problem thus reduces to identifying the spectral edge of $\mathsf{x}$, which we show is dominated by the spectrum of a natural ${n \choose k}$-dimensional matrix from the \emph{Johnson} scheme and is straightforward to compute using known results. To show that our bound is sharp, we construct a witness state with a large quadratic form on $\mathsf{x}$ and transform it into a certificate of a lower bound on the largest quadratic form on $H_{\operatorname{SYK}}$.

Figures

Figures reproduced from arXiv: 2607.27185 by Arpon Basu, Pravesh K. Kothari, Siddhant Midha.

Figure 1
Figure 1. Figure 1: A map of the main results. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗

Review history (2 revisions) →

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

224 extracted references · 2 canonical work pages

  1. [1]

    Physical Review A , volume=

    Good quantum error-correcting codes exist , author=. Physical Review A , volume=. 1996 , publisher=

    1996

  2. [2]

    Proceedings of the Royal Society of London

    Multiple-particle interference and quantum error correction , author=. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences , volume=. 1996 , publisher=

    1996

  3. [4]

    2002 , PAGES =

    Lang, Serge , TITLE =. 2002 , PAGES =. doi:10.1007/978-1-4613-0041-0 , URL =

    doi:10.1007/978-1-4613-0041-0 2002

  4. [5]

    Hamiltonian Sparsification and Gap-Simulation , booktitle =

    Dorit Aharonov and Leo Zhou , editor =. Hamiltonian Sparsification and Gap-Simulation , booktitle =. 2019 , url =. doi:10.4230/LIPIcs.ITCS.2019.2 , timestamp =

    doi:10.4230/lipics.itcs.2019.2 2019

  5. [6]

    doi:10.22331/q-2019-09-30-189 , url =

    The complexity of simulating local measurements on quantum systems , author =. doi:10.22331/q-2019-09-30-189 , url =

    doi:10.22331/q-2019-09-30-189 2019

  6. [7]

    Annales Henri Poincar

    Translationally Invariant Universal Quantum Hamiltonians in 1D , author=. Annales Henri Poincar. 2020 , volume=

    2020

  7. [9]

    arXiv preprint arXiv:2606.09728 , year=

    Quantum Cut Sparsifiers , author=. arXiv preprint arXiv:2606.09728 , year=

    Pith/arXiv arXiv

  8. [10]

    Quantum Inf

    Itai Arad , title =. Quantum Inf. Comput. , volume =. 2011 , url =. doi:10.26421/QIC11.11-12-10 , timestamp =

    doi:10.26421/qic11.11-12-10 2011

  9. [11]

    Hastings , title =

    Matthew B. Hastings , title =. 48th International Colloquium on Automata, Languages, and Programming,. 2021 , url =. doi:10.4230/LIPICS.ICALP.2021.102 , timestamp =

    doi:10.4230/lipics.icalp.2021.102 2021

  10. [12]

    2013 , url =

    Dorit Aharonov and Itai Arad and Thomas Vidick , title =. 2013 , url =. doi:10.1145/2491533.2491549 , timestamp =

    arXiv 2013

  11. [13]

    npj Quantum Information , volume=

    Hamiltonian simulation in the low-energy subspace , author=. npj Quantum Information , volume=. 2021 , publisher=

    2021

  12. [14]

    Quantum , volume=

    Hamiltonian simulation for low-energy states with optimal time dependence , author=. Quantum , volume=. 2024 , publisher=

    2024

  13. [15]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Expander decomposition and pruning: Faster, stronger, and simpler , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    2019

  14. [16]

    arXiv preprint arXiv:2603.24530 , year=

    Fault-Tolerant Distance Oracles Below the n f Barrier , author=. arXiv preprint arXiv:2603.24530 , year=

    arXiv

  15. [17]

    arXiv preprint arXiv:2004.08432 , year=

    Fully-dynamic graph sparsifiers against an adaptive adversary , author=. arXiv preprint arXiv:2004.08432 , year=

    Pith/arXiv arXiv 2004

  16. [18]

    Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Online discrepancy with recourse for vectors and graphs , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

    2022

  17. [19]

    arXiv preprint arXiv:2102.02991 , year=

    Strongly universal Hamiltonian simulators , author=. arXiv preprint arXiv:2102.02991 , year=

    Pith/arXiv arXiv

  18. [20]

    Reservoir-sampling algorithms of time complexity o (n (1+ log (

    Li, Kim-Hung , journal=. Reservoir-sampling algorithms of time complexity o (n (1+ log (. 1994 , publisher=

    1994

  19. [21]

    Physical Review A—Atomic, Molecular, and Optical Physics , volume=

    Quantum-Merlin-Arthur--complete problems for stoquastic Hamiltonians and Markov matrices , author=. Physical Review A—Atomic, Molecular, and Optical Physics , volume=. 2010 , publisher=

    2010

  20. [22]

    John Kallaugher and Ojas Parekh , title =. 63rd. 2022 , url =. doi:10.1109/FOCS54457.2022.00054 , timestamp =

    arXiv 2022

  21. [23]

    Uniform Expansion Bounds for Cayley Graphs of SL_2 (F_p ) , urldate =

    Jean Bourgain and Alex Gamburd , journal =. Uniform Expansion Bounds for Cayley Graphs of SL_2 (F_p ) , urldate =

  22. [24]

    Gross , title =

    Jonathan L. Gross , title =. Journal of Combinatorial Theory, Series B , volume =. 1977 , doi =

    1977

  23. [25]

    Silva, Marcel Kenji de Carli and Harvey, Nicholas J. A. and Sato, Cristiane M. , title =. 2016 , url =. doi:10.1145/2746241 , timestamp =

    doi:10.1145/2746241 2016

  24. [26]

    Journal of Combinatorial Theory, Series A , volume =

    Ervin Gergely , title =. Journal of Combinatorial Theory, Series A , volume =. 1974 , doi =

    1974

  25. [27]

    1979 , institution=

    New results on the independence number , author=. 1979 , institution=

    1979

  26. [28]

    1981 , publisher=

    A lower bound on the stability number of a simple graph , author=. 1981 , publisher=

    1981

  27. [29]

    2015 , volume =

    Foundations and Trends® in Machine Learning , title =. 2015 , volume =. doi:10.1561/2200000048 , issn =

    doi:10.1561/2200000048 2015

  28. [30]

    1986 , isbn =

    Chew, P , title =. 1986 , isbn =. doi:10.1145/10515.10534 , booktitle =

    arXiv 1986

  29. [31]

    Approximating s-t minimum cuts in \

    Bencz\'. Approximating s-t minimum cuts in \. 1996 , isbn =. doi:10.1145/237814.237827 , booktitle =

    arXiv 1996

  30. [32]

    and Teng, Shang-Hua , title =

    Spielman, Daniel A. and Teng, Shang-Hua , title =. SIAM Journal on Computing , volume =. 2011 , doi =

    2011

  31. [33]

    and Srivastava, Nikhil , title =

    Spielman, Daniel A. and Srivastava, Nikhil , title =. SIAM Journal on Computing , volume =. 2011 , doi =

    2011

  32. [34]

    and Srivastava, Nikhil , title =

    Batson, Joshua and Spielman, Daniel A. and Srivastava, Nikhil , title =. SIAM Review , volume =. 2014 , doi =

    2014

  33. [35]

    Code sparsification and its applications , booktitle =

    Khanna, Sanjeev and Putterman, Aaron and Sudan, Madhu , editor =. Code sparsification and its applications , booktitle =. 2024 , url =. doi:10.1137/1.9781611977912.185 , timestamp =

    doi:10.1137/1.9781611977912.185 2024

  34. [36]

    Annals of Mathematics , volume =

    Assaf Naor and Robert Young , title =. Annals of Mathematics , volume =. 2018 , doi =

    2018

  35. [38]

    and Meka, Raghu , title =

    Kane, Daniel M. and Meka, Raghu , title =. 2013 , isbn =. doi:10.1145/2488608.2488610 , booktitle =

    arXiv 2013

  36. [39]

    2002 , issue_date =

    Feige, Uriel and Schechtman, Gideon , title =. 2002 , issue_date =. doi:10.1002/rsa.10036 , journal =

    doi:10.1002/rsa.10036 2002

  37. [40]

    2021 , month =

    Luca Trevisan , title =. 2021 , month =

    2021

  38. [41]

    2025 , archivePrefix=

    Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs , author=. 2025 , archivePrefix=

    2025

  39. [42]

    Spielman , title =

    Daniel A. Spielman , title =. 2019 , url =

    2019

  40. [43]

    Nilli , abstract =

    A. Nilli , abstract =. On the second eigenvalue of a graph , journal =. 1991 , issn =. doi:https://doi.org/10.1016/0012-365X(91)90112-F , url =

    doi:10.1016/0012-365x(91)90112-f 1991

  41. [44]

    and Spielman, Daniel A

    Marcus, Adam W. and Spielman, Daniel A. and Srivastava, Nikhil , TITLE =. Ann. of Math. (2) , FJOURNAL =. 2015 , NUMBER =

    2015

  42. [45]

    2015 , isbn =

    Allen-Zhu, Zeyuan and Liao, Zhenyu and Orecchia, Lorenzo , title =. 2015 , isbn =. doi:10.1145/2746539.2746610 , booktitle =

    arXiv 2015

  43. [46]

    An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification , booktitle =

    Nikhil Srivastava and Luca Trevisan , editor =. An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification , booktitle =. 2018 , url =. doi:10.1137/1.9781611975031.85 , timestamp =

    doi:10.1137/1.9781611975031.85 2018

  44. [47]

    Electronic Journal of Combinatorics , volume =

    Alexandr Polyanskii and Rinat Sadykov , title =. Electronic Journal of Combinatorics , volume =. 2024 , doi =

    2024

  45. [48]

    2018 , archivePrefix=

    Hyperbolic polynomials and the Kadison-Singer problem , author =. 2018 , archivePrefix=

    2018

  46. [49]

    , booktitle=

    Cohen, Michael B. , booktitle=. Ramanujan Graphs in Polynomial Time , year=

  47. [50]

    Journal für die reine und angewandte Mathematik (Crelles Journal) , doi =

    Improved bounds in Weaver and Feichtinger conjectures , author =. Journal für die reine und angewandte Mathematik (Crelles Journal) , doi =. 2019 , lastchecked =

    2019

  48. [51]

    Improved bounds in Weaver's KSr conjecture for high rank positive semidefinite matrices , journal =

    Zhiqiang Xu and Zili Xu and Ziheng Zhu , keywords =. Improved bounds in Weaver's KSr conjecture for high rank positive semidefinite matrices , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.jfa.2023.109978 , url =

    arXiv 2023

  49. [52]

    , title =

    Cohen, Michael B. , title =. 2016 , howpublished =

    2016

  50. [53]

    2012 , URL =

    Why is the minimum size of a generating set for a finite group at most _2 n ? , AUTHOR =. 2012 , URL =

    2012

  51. [54]

    2024 , archivePrefix=

    Selector form of Weaver's conjecture, Feichtinger's conjecture, and frame sparsification , author=. 2024 , archivePrefix=

    2024

  52. [55]

    2024 , url =

    Surya Teja Gavva and Peng Zhang , title =. 2024 , url =

    2024

  53. [56]

    Proceedings of the London Mathematical Society , volume =

    Alon, Noga and Bucić, Matija and Sauermann, Lisa and Zakharov, Dmitrii and Zamir, Or , title =. Proceedings of the London Mathematical Society , volume =. doi:https://doi.org/10.1112/plms.70044 , url =

    doi:10.1112/plms.70044

  54. [57]

    How Abelian is a Finite Group? , booktitle =

    L\'aszl\'o Pyber , editor =. How Abelian is a Finite Group? , booktitle =. 1997 , pages =. doi:10.1007/978-3-642-60408-9_27 , isbn =

    doi:10.1007/978-3-642-60408-9_27 1997

  55. [58]

    Information Theory

    Ash, Robert. Information Theory

  56. [59]

    1994 , issn =

    Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q , journal =. 1994 , issn =. doi:https://doi.org/10.1006/jctb.1994.1054 , url =

    arXiv 1994

  57. [60]

    G. A. Margulis , title =. Problemy Peredachi Informacii , volume =. 1973 , mrnumber =

    1973

  58. [61]

    Lubotzky and R

    A. Lubotzky and R. Phillips and P. Sarnak , title =. Combinatorica , volume =. 1988 , mrnumber =

    1988

  59. [62]

    Combinatorics, Probability and Computing , author=

    Quasirandom Groups , volume=. Combinatorics, Probability and Computing , author=. 2008 , pages=. doi:10.1017/S0963548307008826 , number=

    doi:10.1017/s0963548307008826 2008

  60. [64]

    2025 , isbn =

    Brakensiek, Joshua and Guruswami, Venkatesan , title =. 2025 , isbn =. doi:10.1145/3717823.3718212 , booktitle =

    arXiv 2025

  61. [65]

    Sparsifying Cayley Graphs on Every Group , booktitle =

    Jun. Sparsifying Cayley Graphs on Every Group , booktitle =. 2026 , url =. doi:10.1137/1.9781611978971.215 , timestamp =

    doi:10.1137/1.9781611978971.215 2026

  62. [67]

    Liu and Aaron Sidford , editor =

    Arun Jambulapati and Yang P. Liu and Aaron Sidford , editor =. Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification , booktitle =. 2023 , url =. doi:10.1145/3564246.3585136 , timestamp =

    arXiv 2023

  63. [68]

    Kothari and Yang P

    Arpon Basu and Pravesh K. Kothari and Yang P. Liu and Raghu Meka , title =. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. doi:10.1137/1.9781611978971.216 , URL =

    doi:10.1137/1.9781611978971.216 2026

  64. [69]

    Karger , editor =

    David R. Karger , editor =. Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm , booktitle =. 1993 , url =

    1993

  65. [70]

    A Theory of Spectral

    Sanjeev Khanna and Aaron Putterman and Madhu Sudan , editor =. A Theory of Spectral. 52nd International Colloquium on Automata, Languages, and Programming,. 2025 , url =. doi:10.4230/LIPIcs.ICALP.2025.107 , timestamp =

    doi:10.4230/lipics.icalp.2025.107 2025

  66. [71]

    2017 , url =

    Arnold Filtser and Robert Krauthgamer , title =. 2017 , url =. doi:10.1137/15M1046186 , timestamp =

    doi:10.1137/15m1046186 2017

  67. [72]

    On Fully Dynamic Graph Sparsifiers , booktitle =

    Ittai Abraham and David Durfee and Ioannis Koutis and Sebastian Krinninger and Richard Peng , editor =. On Fully Dynamic Graph Sparsifiers , booktitle =. 2016 , url =. doi:10.1109/FOCS.2016.44 , timestamp =

    doi:10.1109/focs.2016.44 2016

  68. [73]

    Benson and Jon M

    Nate Veldt and Austin R. Benson and Jon M. Kleinberg , title =. 2022 , url =. doi:10.1137/20m1321048 , timestamp =

    doi:10.1137/20m1321048 2022

  69. [74]

    Sketching Cuts in Graphs and Hypergraphs , booktitle =

    Dmitry Kogan and Robert Krauthgamer , editor =. Sketching Cuts in Graphs and Hypergraphs , booktitle =. 2015 , url =. doi:10.1145/2688073.2688093 , timestamp =

    arXiv 2015

  70. [75]

    Spectral Sparsification of Hypergraphs , booktitle =

    Tasuku Soma and Yuichi Yoshida , editor =. Spectral Sparsification of Hypergraphs , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.159 , timestamp =

    doi:10.1137/1.9781611975482.159 2019

  71. [76]

    Michael Kapralov and Robert Krauthgamer and Jakab Tardos and Yuichi Yoshida , title =. 62nd. 2021 , url =. doi:10.1109/FOCS52979.2021.00114 , timestamp =

    arXiv 2021

  72. [77]

    Towards tight bounds for spectral sparsification of hypergraphs , booktitle =

    Michael Kapralov and Robert Krauthgamer and Jakab Tardos and Yuichi Yoshida , editor =. Towards tight bounds for spectral sparsification of hypergraphs , booktitle =. 2021 , url =. doi:10.1145/3406325.3451061 , timestamp =

    arXiv 2021

  73. [78]

    Sanjeev Khanna and Aaron Putterman and Madhu Sudan , title =. 65th. 2024 , url =. doi:10.1109/FOCS61266.2024.00105 , timestamp =

    arXiv 2024

  74. [79]

    Near-linear Size Hypergraph Cut Sparsifiers , booktitle =

    Yu Chen and Sanjeev Khanna and Ansh Nagda , editor =. Near-linear Size Hypergraph Cut Sparsifiers , booktitle =. 2020 , url =. doi:10.1109/FOCS46700.2020.00015 , timestamp =

    arXiv 2020

  75. [80]

    CoRR , volume =

    Joshua Brakensiek and Venkatesan Guruswami and Aaron Putterman , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2508.13345 , eprinttype =

    doi:10.48550/arxiv.2508.13345 2025

  76. [81]

    Analyzing graph structure via linear measurements , booktitle =

    Kook Jin Ahn and Sudipto Guha and Andrew McGregor , editor =. Analyzing graph structure via linear measurements , booktitle =. 2012 , url =. doi:10.1137/1.9781611973099.40 , timestamp =

    doi:10.1137/1.9781611973099.40 2012

  77. [82]

    Graph sketches: sparsification, spanners, and subgraphs , booktitle =

    Kook Jin Ahn and Sudipto Guha and Andrew McGregor , editor =. Graph sketches: sparsification, spanners, and subgraphs , booktitle =. 2012 , url =. doi:10.1145/2213556.2213560 , timestamp =

    arXiv 2012

  78. [83]

    Sparsification of Directed Graphs via Cut Balance , booktitle =

    Ruoxu Cen and Yu Cheng and Debmalya Panigrahi and Kevin Sun , editor =. Sparsification of Directed Graphs via Cut Balance , booktitle =. 2021 , url =. doi:10.4230/LIPIcs.ICALP.2021.45 , timestamp =

    doi:10.4230/lipics.icalp.2021.45 2021

  79. [84]

    and Panigrahi, Debmalya , title =

    Fung, Wai Shing and Hariharan, Ramesh and Harvey, Nicholas J.A. and Panigrahi, Debmalya , title =. Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing , pages =. 2011 , isbn =. doi:10.1145/1993636.1993647 , abstract =

    arXiv 2011

  80. [85]

    Sparsification of

    Butti, Silvia and. Sparsification of. 2020 , month = jan, journal =

    2020

Showing first 80 references.