Pith. sign in

REVIEW 4 minor 2 cited by

Sharp Bounds on Ground State Energy of the SYK Model

T0 review · 0 major / 4 minor · reviewed 2026-07-30 · grok-4.5

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

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

desk verdict 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. read the letter →

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

Arpon Basu , Pravesh K. Kothari , Siddhant Midha This is my paper · ORCID
classification quant-phmath.PR MSC 81Q1060B2005E3015B52 PACS 05.30.-d03.65.Fd05.45.Mt
keywords SYKmodeloperatornormground-stateenergytwistedbosonsJohnsonschemesparsetracemomentsMajoranafermions
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

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.

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

Extended reading notes

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.

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.

Editorial extensions

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→∞.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, 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 · score 0.0 of 10

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).

Assumptions & free parameters 0 free parameters · 6 assumptions · 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.

assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sharp Bounds on Ground State Energy of the SYK Model." pith.science (2026). https://pith.science/paper/XRLWPYKV

@misc{pith2026260727185,
  author       = {Pith},
  title        = {Pith review of: Sharp Bounds on Ground State Energy of the SYK Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XRLWPYKV}},
  note         = {Machine review of arXiv:2607.27185}
}
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 the authors.

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). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Weak local law and delocalization for the Sachdev-Ye-Kitaev model

    math.PR 2026-08 conditional novelty 8.0 of 10

    For the SYK model with even q much smaller than sqrt(N), local eigenvalue statistics match a Gaussian law down to scales q/sqrt(N), and eigenvectors delocalize in any deterministic basis.

  2. The spectral edge of the quartic SYK model

    math-ph 2026-07 conditional novelty 8.0 of 10

    For the q=4 SYK model, λ₁/√N → 0.325042158... almost surely, the value fixed by the zero-temperature Schwinger–Dyson equation.

Reference graph

Works this paper leans on

224 extracted references · 2 canonical work pages · cited by 2 Pith papers

  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=

    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

Show all 224 references
  1. [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 =

    2021 doi

  2. [12]

    2013 , url =

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

    2013

  3. [13]

    npj Quantum Information , volume=

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

    2021

  4. [14]

    Quantum , volume=

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

    2024

  5. [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

  6. [16]

    arXiv preprint arXiv:2603.24530 , year=

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

  7. [17]

    arXiv preprint arXiv:2004.08432 , year=

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

    2004 arXiv

  8. [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

  9. [19]

    arXiv preprint arXiv:2102.02991 , year=

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

    arXiv

  10. [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

  11. [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

  12. [22]

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

    2022

  13. [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 =

  14. [24]

    Gross , title =

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

    1977

  15. [25]

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

    2016 doi

  16. [26]

    Journal of Combinatorial Theory, Series A , volume =

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

    1974

  17. [27]

    1979 , institution=

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

    1979

  18. [28]

    1981 , publisher=

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

    1981

  19. [29]

    2015 , volume =

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

    2015 doi

  20. [30]

    1986 , isbn =

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

    1986

  21. [31]

    Approximating s-t minimum cuts in \

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

    1996

  22. [32]

    and Teng, Shang-Hua , title =

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

    2011

  23. [33]

    and Srivastava, Nikhil , title =

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

    2011

  24. [34]

    and Srivastava, Nikhil , title =

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

    2014

  25. [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 =

    2024 doi

  26. [36]

    Annals of Mathematics , volume =

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

    2018

  27. [38]

    and Meka, Raghu , title =

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

    2013

  28. [39]

    2002 , issue_date =

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

    2002 doi

  29. [40]

    2021 , month =

    Luca Trevisan , title =. 2021 , month =

    2021

  30. [41]

    2025 , archivePrefix=

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

    2025

  31. [42]

    Spielman , title =

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

    2019

  32. [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 =

    1991 doi

  33. [44]

    and Spielman, Daniel A

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

    2015

  34. [45]

    2015 , isbn =

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

    2015

  35. [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 =

    2018 doi

  36. [47]

    Electronic Journal of Combinatorics , volume =

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

    2024

  37. [48]

    2018 , archivePrefix=

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

    2018

  38. [49]

    , booktitle=

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

  39. [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

  40. [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 =

    2023

  41. [52]

    , title =

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

    2016

  42. [53]

    2012 , URL =

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

    2012

  43. [54]

    2024 , archivePrefix=

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

    2024

  44. [55]

    2024 , url =

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

    2024

  45. [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

  46. [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 =

    1997 doi

  47. [58]

    Information Theory

    Ash, Robert. Information Theory

  48. [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 =

    1994

  49. [60]

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

    1973

  50. [61]

    Lubotzky and R

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

    1988

  51. [62]

    Combinatorics, Probability and Computing , author=

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

    2008 doi

  52. [64]

    2025 , isbn =

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

    2025

  53. [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 =

    2026 doi

  54. [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 =

    2023

  55. [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 =

    2026 doi

  56. [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

  57. [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 =

    2025 doi

  58. [71]

    2017 , url =

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

    2017 doi

  59. [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 =

    2016 doi

  60. [73]

    Benson and Jon M

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

    2022 doi

  61. [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 =

    2015

  62. [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 =

    2019 doi

  63. [76]

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

    2021

  64. [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 =

    2021

  65. [78]

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

    2024

  66. [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 =

    2020

  67. [80]

    CoRR , volume =

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

    2025 doi

  68. [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 =

    2012 doi

  69. [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 =

    2012

  70. [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 =

    2021 doi

  71. [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 =

    2011

  72. [85]

    Sparsification of

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

    2020

  73. [86]

    On Redundancy in Constraint Satisfaction Problems , booktitle =

    Cl. On Redundancy in Constraint Satisfaction Problems , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.CP.2022.11 , timestamp =

    2022 doi

  74. [87]

    Joshua Brakensiek and Venkatesan Guruswami and Bart M. P. Jansen and Victor Lagerkvist and Magnus Wahlstr. The Richness of. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2507.07942 , eprinttype =

    2025 doi

  75. [88]

    Chen, Hubie and Jansen, Bart M. P. and Pieterse, Astrid , year =. Best-. Algorithmica , volume =. doi:10.1007/s00453-019-00660-y , langid =

    doi

  76. [89]

    Sparsification of

    Lagerkvist, Victor and Wahlstr. Sparsification of. 2020 , month = jun, journal =. doi:10.1145/3389411 , langid =

    2020 doi

  77. [90]

    Bessiere, Christian and Carbonnel, Cl. Chain. 2020 , month = apr, journal =. doi:10.1609/aaai.v34i02.5499 , copyright =

    2020 doi

  78. [91]

    Constraint Acquisition via Partial Queries , booktitle =

    Christian Bessiere and Remi Coletta and Emmanuel Hebrard and George Katsirelos and Nadjib Lazaar and Nina Narodytska and Claude. Constraint Acquisition via Partial Queries , booktitle =. 2013 , url =

    2013

  79. [92]

    Optimal Lower Bounds for Sketching Graph Cuts , booktitle =

    Charles Carlson and Alexandra Kolla and Nikhil Srivastava and Luca Trevisan , editor =. Optimal Lower Bounds for Sketching Graph Cuts , booktitle =. 2019 , url =. doi:10.1137/1.9781611975482.158 , timestamp =

    2019 doi

  80. [93]

    Bart M. P. Jansen and Astrid Pieterse , title =. 2019 , url =. doi:10.1145/3349618 , timestamp =

    2019 doi

  81. [94]

    Satisfiability

    Dell, Holger and van Melkebeek, Dieter , year =. Satisfiability. J. ACM , volume =

  82. [95]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=. 2026 , doi=

    2026

  83. [96]

    2026 , archivePrefix=

    Classification of Non-redundancy of Boolean Predicates of Arity 4 , author=. 2026 , archivePrefix=

    2026

  84. [97]

    Whiston, Julius , TITLE =. J. Algebra , FJOURNAL =. 2000 , NUMBER =. doi:10.1006/jabr.2000.8399 , URL =

    2000

  85. [98]

    Valued Constraint Satisfaction Problems: Hard and Easy Problems , booktitle =

    Thomas Schiex and H. Valued Constraint Satisfaction Problems: Hard and Easy Problems , booktitle =. 1995 , url =

    1995

  86. [99]

    1965 , publisher=

    Analytic Functions of Several Complex Variables , author=. 1965 , publisher=

    1965

  87. [100]

    Morampudi and Chris R

    Or Sattath and Siddhardh C. Morampudi and Chris R. Laumann and Roderich Moessner , title =. Proceedings of the National Academy of Sciences , volume =. 2016 , doi =

    2016

  88. [101]

    Communications in Mathematical Physics , volume=

    Stability of frustration-free Hamiltonians , author=. Communications in Mathematical Physics , volume=. 2013 , publisher=

    2013

  89. [102]

    Quantum Hamiltonian complexity and the detectability lemma , author=

  90. [103]

    arXiv preprint arXiv:2003.14394 , year=

    Beyond product state approximations for a quantum analogue of max cut , author=. arXiv preprint arXiv:2003.14394 , year=

    2003 arXiv

  91. [104]

    arXiv preprint arXiv:2504.15276 , year=

    Improved algorithms for quantum maxcut via partially entangled matchings , author=. arXiv preprint arXiv:2504.15276 , year=

    arXiv

  92. [105]

    Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

    Product-state approximations to quantum ground states , author=. Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

  93. [106]

    arXiv preprint arXiv:1909.08846 , year=

    Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut , author=. arXiv preprint arXiv:1909.08846 , year=

    1909 arXiv

  94. [107]

    arXiv preprint arXiv:2504.11120 , year=

    Improved approximation ratios for the Quantum Max-Cut problem on general, triangle-free and bipartite graphs , author=. arXiv preprint arXiv:2504.11120 , year=

    arXiv

  95. [108]

    arXiv preprint arXiv:2411.04120 , year=

    Second order cone relaxations for quantum Max Cut , author=. arXiv preprint arXiv:2411.04120 , year=

    arXiv

  96. [109]

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

    Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  97. [110]

    Quantum , volume=

    An improved approximation algorithm for quantum max-cut on triangle-free graphs , author=. Quantum , volume=. 2023 , publisher=

    2023

  98. [111]

    arXiv preprint arXiv:2401.03616 , year=

    An improved Quantum Max Cut approximation via matching , author=. arXiv preprint arXiv:2401.03616 , year=

  99. [112]

    arXiv preprint arXiv:2510.07995 , year=

    Quantum Max-Cut is NP hard to approximate , author=. arXiv preprint arXiv:2510.07995 , year=

  100. [113]

    arXiv preprint arXiv:2206.08342 , year=

    An optimal product-state approximation for 2-local quantum Hamiltonians with positive terms , author=. arXiv preprint arXiv:2206.08342 , year=

  101. [114]

    Cross disciplinary advances in quantum computing , SERIES =

    Bravyi, Sergey , TITLE =. Cross disciplinary advances in quantum computing , SERIES =. 2011 , ISBN =. doi:10.1090/conm/536/10552 , URL =

    2011 doi

  102. [115]

    Niel de Beaudrap and Sevag Gharibian , editor =

    J. Niel de Beaudrap and Sevag Gharibian , editor =. A Linear Time Algorithm for Quantum 2-SAT , booktitle =. 2016 , url =. doi:10.4230/LIPIcs.CCC.2016.27 , timestamp =

    2016 doi

  103. [116]

    2016 , url =

    David Gosset and Daniel Nagaj , title =. 2016 , url =. doi:10.1137/140957056 , timestamp =

    2016 doi

  104. [117]

    Quantum Inf

    Stephen Piddock and Ashley Montanaro , title =. Quantum Inf. Comput. , volume =. 2017 , url =. doi:10.26421/QIC17.7-8-6 , timestamp =

    2017 doi

  105. [118]

    Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality , booktitle =

    Yeongwoo Hwang and Joe Neeman and Ojas Parekh and Kevin Thompson and John Wright , editor =. Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.ch48 , timestamp =

    2023 doi

  106. [119]

    CoRR , volume =

    Stephen Piddock , title =. CoRR , volume =. 2025 , url =. doi:10.48550/arXiv.2510.07995 , eprinttype =

    2025 doi

  107. [120]

    Cubitt and Ashley Montanaro , title =

    Toby S. Cubitt and Ashley Montanaro , title =. 2016 , url =. doi:10.1137/140998287 , timestamp =

    2016 doi

  108. [121]

    Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut , booktitle =

    Sevag Gharibian and Ojas Parekh , editor =. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut , booktitle =. 2019 , url =. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.31 , timestamp =

    2019 doi

  109. [122]

    An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube , volume=

    Filmus, Yuval , year=. An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube , volume=. The Electronic Journal of Combinatorics , publisher=. doi:10.37236/4567 , number=

    doi

  110. [123]

    Alon, Gil and Kozma, Gady , TITLE =. Ann. Inst. Henri Poincar\'. 2020 , NUMBER =. doi:10.1214/20-AIHP1054 , URL =

    2020 doi

  111. [124]

    and Richthammer, Thomas , TITLE =

    Caputo, Pietro and Liggett, Thomas M. and Richthammer, Thomas , TITLE =. J. Amer. Math. Soc. , FJOURNAL =. 2010 , NUMBER =. doi:10.1090/S0894-0347-10-00659-4 , URL =

    2010 doi

  112. [125]

    and Peres, Yuval , TITLE =

    Morris, B. and Peres, Yuval , TITLE =. Probab. Theory Related Fields , FJOURNAL =. 2005 , NUMBER =. doi:10.1007/s00440-005-0434-7 , URL =

    2005 doi

  113. [126]

    Dunkl , journal =

    Charles F. Dunkl , journal =. A Krawtchouk Polynomial Addition Theorem and Wreath Products of Symmetric Groups , urldate =

  114. [127]

    Combinatorica , year =

    Dikstein, Yotam and Dinur, Irit and Filmus, Yuval and Harsha, Prahladh , title =. Combinatorica , year =. doi:10.1007/s00493-024-00084-5 , url =

    doi

  115. [128]

    2010 , url =

    Chris Godsil , title =. 2010 , url =

    2010

  116. [129]

    2026 , eprint=

    Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut , author=. 2026 , eprint=

    2026

  117. [130]

    , title =

    Grigoriev, D. , title =. computational complexity , year =. doi:10.1007/s00037-001-8192-0 , url =

    doi

  118. [131]

    2026 , eprint=

    Many Hamiltonians Are Sparsifiable , author=. 2026 , eprint=

    2026

  119. [132]

    Diaconis, Persi and Shahshahani, Mehrdad , TITLE =. Z. Wahrsch. Verw. Gebiete , FJOURNAL =. 1981 , NUMBER =. doi:10.1007/BF00535487 , URL =

    1981 doi

  120. [133]

    Diaconis, Persi and Saloff-Coste, Laurent , TITLE =. Ann. Appl. Probab. , FJOURNAL =. 1993 , NUMBER =

    1993

  121. [134]

    and Peres, Yuval and Wilmer, Elizabeth L

    Levin, David A. and Peres, Yuval and Wilmer, Elizabeth L. , TITLE =. 2009 , PAGES =. doi:10.1090/mbk/058 , URL =

    2009 doi

  122. [135]

    and Odlyzko, A

    Flatto, L. and Odlyzko, A. M. and Wales, D. B. , TITLE =. Ann. Probab. , FJOURNAL =. 1985 , NUMBER =

    1985

  123. [136]

    Cesi, Filippo , TITLE =. J. Algebraic Combin. , FJOURNAL =. 2010 , NUMBER =. doi:10.1007/s10801-009-0208-x , URL =

    2010 doi

  124. [137]

    Handjani, Shirin and Jungreis, Douglas , TITLE =. J. Theoret. Probab. , FJOURNAL =. 1996 , NUMBER =. doi:10.1007/BF02214260 , URL =

    1996 doi

  125. [138]

    , TITLE =

    Chen, Joe P. , TITLE =. Electron. Commun. Probab. , FJOURNAL =. 2017 , PAGES =. doi:10.1214/17-ECP82 , URL =

    2017 doi

  126. [139]

    Alon, Gil and Kozma, Gady and Puder, Doron , TITLE =. Math. Proc. Cambridge Philos. Soc. , FJOURNAL =. 2025 , NUMBER =. doi:10.1017/S0305004125000179 , URL =

    2025 doi

  127. [140]

    and Manohar, Peter , title =

    Guruswami, Venkatesan and Kothari, Pravesh K. and Manohar, Peter , title =. 2022 , isbn =. doi:10.1145/3519935.3519955 , booktitle =

    2022

  128. [141]

    Kothari and Sidhanth Mohanty , title =

    Jun-Ting Hsieh and Pravesh K. Kothari and Sidhanth Mohanty , title =. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. doi:10.1137/1.9781611977554.ch89 , URL =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611977554.ch89 , year =

    2023 doi

  129. [142]

    Kothari and Peter Manohar , title =

    Omar Alrabiah and Venkatesan Guruswami and Pravesh K. Kothari and Peter Manohar , title =. Proceedings of the 55th Annual

  130. [143]

    Kothari and Peter Manohar , title =

    Pravesh K. Kothari and Peter Manohar , title =. Proceedings of the 56th Annual

  131. [144]

    and Lin, Andrew D

    Basu, Arpon and Hsieh, Jun-Ting and Kothari, Pravesh K. and Lin, Andrew D. , booktitle=. Improved Lower Bounds for all Odd-Query Locally Decodable Codes , year=

  132. [145]

    2025 , pages =

    Janzer, Oliver and Manohar, Peter , booktitle =. 2025 , pages =. doi:10.1109/FOCS63196.2025.00009 , url =

    2025

  133. [146]

    2025 , issue_date =

    Wein, Alexander and El Alaoui, Ahmed and Moore, Cristopher , title =. 2025 , issue_date =. doi:10.1145/3762806 , articleno =

    2025 doi

  134. [147]

    Stronger Cell Probe Lower Bounds via Local PRGs , year=

    Korten, Oliver and Pitassi, Toniann and Impagliazzo, Russell , booktitle=. Stronger Cell Probe Lower Bounds via Local PRGs , year=

  135. [148]

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

    Venkatesan Guruswami and Xin Lyu and Weiqiang Yuan , title =. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. doi:10.1137/1.9781611978971.17 , year =. https://epubs.siam.org/doi/pdf/10.1137/1.9781611978971.17 , abstract =

    2026 doi

  136. [149]

    ArXiv , year=

    Conjectured Bounds for 2-Local Hamiltonians via Token Graphs , author=. ArXiv , year=

  137. [150]

    2026 , eprint=

    Aldous-type Spectral Gaps in Unitary Groups , author=. 2026 , eprint=

    2026

  138. [151]

    Spielman , title =

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

    2025

  139. [152]

    2002 , NOTE =

    Aldous, David and Fill, James Allen , TITLE =. 2002 , NOTE =

    2002

  140. [153]

    Stanley , journal =

    Richard P. Stanley , journal =. Differential Posets , volume =. 1988 , url =

    1988

  141. [154]

    Feige, Uriel , booktitle=

  142. [155]

    Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold , booktitle =

    Venkatesan Guruswami and Jun. Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold , booktitle =

  143. [156]

    Lin and Peter Manohar , year=

    Arpon Basu and Jun-Ting Hsieh and Andrew D. Lin and Peter Manohar , year=. Solving Random Planted CSPs below the n^. 2507.10833 , archivePrefix=

    arXiv

  144. [157]

    2026 , eprint=

    Kikuchi Graphs of Random Hypergraphs are Approximately Johnson , author=. 2026 , eprint=

    2026

  145. [158]

    and Teng, Shang-Hua , title =

    Spielman, Daniel A. and Teng, Shang-Hua , title =. Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing , pages =. 2004 , isbn =. doi:10.1145/1007352.1007372 , abstract =

    2004

  146. [159]

    SIAM Journal on Computing , volume=

    Single pass spectral sparsification in dynamic streams , author=. SIAM Journal on Computing , volume=. 2017 , publisher=

    2017

  147. [160]

    ACM SIGMOD Record , volume=

    Graph stream algorithms: a survey , author=. ACM SIGMOD Record , volume=. 2014 , publisher=

    2014

  148. [161]

    Random Structures & Algorithms , volume=

    Random Cayley graphs and expanders , author=. Random Structures & Algorithms , volume=. 1994 , publisher=

    1994

  149. [162]

    41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) , pages =

    Jalan, Akhil and Moshkovitz, Dana , title =. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) , pages =. 2021 , volume =. doi:10.4230/LIPIcs.FSTTCS.2021.24 , annote =

    2021 doi

  150. [163]

    Theory of Computing , volume=

    Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications , author=. Theory of Computing , volume=. 2008 , publisher=

    2008

  151. [164]

    SIAM Journal on Computing , volume=

    Constructive discrepancy minimization for convex sets , author=. SIAM Journal on Computing , volume=. 2017 , publisher=

    2017

  152. [165]

    Bravyi and Alexei Yu

    Sergey B. Bravyi and Alexei Yu. Kitaev , abstract =. Fermionic Quantum Computation , journal =. 2002 , issn =. doi:https://doi.org/10.1006/aphy.2002.6254 , url =

    2002

  153. [166]

    , title =

    Isserlis, L. , title =. Biometrika , volume =. 1918 , month =. doi:10.1093/biomet/12.1-2.134 , url =

    1918 doi

  154. [167]

    The Evaluation of the Collision Matrix , author =. Phys. Rev. , volume =. 1950 , month =. doi:10.1103/PhysRev.80.268 , url =

    1950 doi

  155. [168]

    and Chen, Chi-Fang and Kiani, Bobak T

    Anschuetz, Eric R. and Chen, Chi-Fang and Kiani, Bobak T. and King, Robbie , year = 2025, month = jul, journal =. Strongly. doi:10.1103/cbqf-d24r , urldate =

    2025 doi

  156. [169]

    and Anschuetz, Eric R

    Ding, Matthew and King, Robbie and Kiani, Bobak T. and Anschuetz, Eric R. , year = 2026, month = mar, journal =. Optimizing. doi:10.22331/q-2026-03-16-2029 , urldate =. arXiv , keywords =:2506.09037 , primaryclass =

    2026

  157. [170]

    Quantum , volume=

    Optimizing sparse fermionic Hamiltonians , author=. Quantum , volume=. 2023 , publisher=

    2023

  158. [171]

    A Rigorous Quasipolynomial-Time Classical Algorithm for

    Zlokapa, Alexander , year = 2026, month = apr, number =. A Rigorous Quasipolynomial-Time Classical Algorithm for. doi:10.48550/arXiv.2604.21089 , urldate =. arXiv , keywords =:2604.21089 , primaryclass =

    2026 doi arXiv

  159. [172]

    , year = 2026, month = feb, number =

    Zlokapa, Alexander and Kiani, Bobak T. , year = 2026, month = feb, number =. doi:10.48550/arXiv.2602.22619 , urldate =. 2602.22619 , primaryclass =

    2026 doi arXiv

  160. [173]

    Gapless spin-fluid ground state in a random quantum Heisenberg magnet , author =. Phys. Rev. Lett. , volume =. 1993 , month =. doi:10.1103/PhysRevLett.70.3339 , url =

    1993 doi

  161. [174]

    Entanglement in strongly-correlated quantum matter , pages=

    A simple model of quantum holography , author=. Entanglement in strongly-correlated quantum matter , pages=

  162. [175]

    Remarks on the Sachdev-Ye-Kitaev model , author =. Phys. Rev. D , volume =. 2016 , month =. doi:10.1103/PhysRevD.94.106002 , url =

    2016 doi

  163. [176]

    arXiv preprint arXiv:2605.02768 , year=

    The free energy limit of the SYK model at high temperature , author=. arXiv preprint arXiv:2605.02768 , year=

    arXiv

  164. [177]

    Peking Mathematical Journal , volume=

    Spectrum of SYK model , author=. Peking Mathematical Journal , volume=. 2019 , publisher=

    2019

  165. [178]

    Random Matrices: Theory and Applications , volume=

    Spectrum of SYK model II: Central limit theorem , author=. Random Matrices: Theory and Applications , volume=. 2021 , publisher=

    2021

  166. [179]

    Random Matrices: Theory and Applications , volume=

    Spectrum of SYK model III: Large deviations and concentration of measures , author=. Random Matrices: Theory and Applications , volume=. 2020 , publisher=

    2020

  167. [180]

    Spectral and thermodynamic properties of the Sachdev-Ye-Kitaev model , author =. Phys. Rev. D , volume =. 2016 , month =. doi:10.1103/PhysRevD.94.126010 , url =

    2016 doi

  168. [181]

    Analytical spectral density of the Sachdev-Ye-Kitaev model at finite N , author =. Phys. Rev. D , volume =. 2017 , month =. doi:10.1103/PhysRevD.96.066012 , url =

    2017 doi

  169. [182]

    Journal of High Energy Physics , volume=

    Exact moments of the Sachdev-Ye-Kitaev model up to order 1/N2 , author=. Journal of High Energy Physics , volume=. 2018 , publisher=

    2018

  170. [183]

    Journal of High Energy Physics , volume=

    Large N expansion of the moments and free energy of Sachdev-Ye-Kitaev model, and the enumeration of intersection graphs , author=. Journal of High Energy Physics , volume=. 2018 , publisher=

    2018

  171. [184]

    Journal of High Energy Physics , volume=

    Chord diagrams, exact correlators in spin glasses and black hole bulk reconstruction , author=. Journal of High Energy Physics , volume=. 2018 , publisher=

    2018

  172. [185]

    Journal of High Energy Physics , volume=

    Towards a full solution of the large N double-scaled SYK model , author=. Journal of High Energy Physics , volume=. 2019 , publisher=

    2019

  173. [186]

    Reports on Progress in Physics , volume=

    A cordial introduction to double scaled SYK , author=. Reports on Progress in Physics , volume=. 2025 , publisher=

    2025

  174. [187]

    Sachdev-Ye-Kitaev models and beyond: Window into non-Fermi liquids , author =. Rev. Mod. Phys. , volume =. 2022 , month =. doi:10.1103/RevModPhys.94.035004 , url =

    2022 doi

  175. [188]

    Journal of High Energy Physics , volume=

    The bulk Hilbert space of double scaled SYK , author=. Journal of High Energy Physics , volume=. 2022 , publisher=

    2022

  176. [189]

    Journal of High Energy Physics , volume=

    The spectrum in the Sachdev-Ye-Kitaev model , author=. Journal of High Energy Physics , volume=. 2016 , publisher=

    2016

  177. [190]

    Communications in Mathematical Physics , volume=

    An example of a generalized Brownian motion , author=. Communications in Mathematical Physics , volume=. 1991 , publisher=

    1991

  178. [191]

    Journal of Physics A: Mathematical and Theoretical , volume=

    An introduction to the SYK model , author=. Journal of Physics A: Mathematical and Theoretical , volume=. 2019 , publisher=

    2019

  179. [192]

    Proceedings of the 54th annual ACM SIGACT symposium on theory of computing , pages=

    Optimizing strongly interacting fermionic Hamiltonians , author=. Proceedings of the 54th annual ACM SIGACT symposium on theory of computing , pages=

  180. [193]

    arXiv preprint arXiv:2411.02578 , year=

    Optimizing random local Hamiltonians by dissipation , author=. arXiv preprint arXiv:2411.02578 , year=

    arXiv

  181. [194]

    2018 , publisher=

    High-dimensional probability: An introduction with applications in data science , author=. 2018 , publisher=

    2018

  182. [195]

    1997 , publisher=

    Gaussian hilbert spaces , author=. 1997 , publisher=

    1997

  183. [196]

    Physics Letters B , volume=

    Validity of random matrix theories for many-particle systems , author=. Physics Letters B , volume=. 1970 , publisher=

    1970

  184. [197]

    Physics Letters B , volume=

    Two-body random Hamiltonian and level density , author=. Physics Letters B , volume=. 1971 , publisher=

    1971

  185. [198]

    Journal of High Energy Physics , volume=

    A bound on chaos , author=. Journal of High Energy Physics , volume=. 2016 , publisher=

    2016

  186. [199]

    arXiv preprint arXiv:2008.02303 , year=

    A sparse model of quantum holography , author=. arXiv preprint arXiv:2008.02303 , year=

    2008 arXiv

  187. [200]

    Nature , volume=

    Traversable wormhole dynamics on a quantum processor , author=. Nature , volume=. 2022 , publisher=

    2022

  188. [201]

    2026 , eprint=

    The spectral edge of the quartic SYK model , author=. 2026 , eprint=

    2026

  189. [202]

    Journal of Mathematical Physics , volume=

    Parastochastics , author=. Journal of Mathematical Physics , volume=. 1970 , publisher=

    1970

  190. [203]

    Communications in Mathematical Physics , volume=

    q-Gaussian processes: non-commutative and classical aspects , author=. Communications in Mathematical Physics , volume=. 1997 , publisher=

    1997

  191. [204]

    arXiv preprint arXiv:1505.07852 , year=

    Ultraproduct methods for mixed q -Gaussian algebras , author=. arXiv preprint arXiv:1505.07852 , year=

    arXiv

  192. [205]

    Random Matrices: Theory and Applications , volume=

    A dynamical version of the SYK model and the q-Brownian motion , author=. Random Matrices: Theory and Applications , volume=. 2022 , publisher=

    2022

  193. [206]

    arXiv preprint arXiv:2602.00789 , year=

    Limit joint distributions of SYK Models with partial interactions, Mixed q-Gaussian Models and Asymptotic varepsilon-freeness , author=. arXiv preprint arXiv:2602.00789 , year=

    arXiv

  194. [207]

    Variational wave functions for Sachdev-Ye-Kitaev models , author =. Phys. Rev. Res. , volume =. 2021 , month =. doi:10.1103/PhysRevResearch.3.023020 , url =

    2021 doi

  195. [208]

    Gamarnik, BT Kiani , author=

    Bounds on the Ground State Energy of Quantum p-Spin Hamiltonians: ER Anschuetz, D. Gamarnik, BT Kiani , author=. Communications in Mathematical Physics , volume=. 2025 , publisher=

    2025

  196. [209]

    2015 , publisher=

    Erdos--Ko--Rado theorems: algebraic approaches , author=. 2015 , publisher=

    2015

  197. [210]

    Philips Res

    An algebraic approach to the association schemes of coding theory , author=. Philips Res. Rep. Suppl. , volume=

  198. [211]

    arXiv preprint arXiv:1406.0142 , year=

    Orthogonal basis for functions over a slice of the Boolean hypercube , author=. arXiv preprint arXiv:1406.0142 , year=

    arXiv

  199. [212]

    2021 , eprint=

    Analysis of Boolean Functions , author=. 2021 , eprint=

    2021

  200. [213]

    1990 , issn =

    A Diagonal Form for the Incidence Matrices of t-Subsets vs.k-Subsets , journal =. 1990 , issn =. doi:https://doi.org/10.1016/S0195-6698(13)80046-7 , url =

    1990 doi

  201. [214]

    A quartic interaction in two dimensions

    Nelson, E. A quartic interaction in two dimensions. Mathematical Theory of Elementary Particles, Proc. Conf., Dedham, Mass., 1965. 1966

    1965

  202. [215]

    1973 , issn =

    Construction of quantum fields from Markoff fields , journal =. 1973 , issn =. doi:https://doi.org/10.1016/0022-1236(73)90091-8 , url =

    1973 doi

  203. [216]

    Logarithmic Sobolev Inequalities , urldate =

    Leonard Gross , journal =. Logarithmic Sobolev Inequalities , urldate =

  204. [217]

    Quantum spin glasses and Sachdev-Ye-Kitaev models

    Sachdev, Subir. Quantum spin glasses and Sachdev-Ye-Kitaev models. 2024. arXiv:2402.17824

    2024 arXiv

  205. [218]

    arXiv: High Energy Physics - Theory , year=

    MAPPINGS OF MULTIMODE BOSE ALGEBRA PRESERVING NUMBER OPERATORS , author =. arXiv: High Energy Physics - Theory , year=

  206. [219]

    and Milekovi \'c , M

    Meljanac, S. and Milekovi \'c , M. A unified view of multimode algebras with Fock-like representations. Int. J. Mod. Phys. A. 1996. doi:10.1142/S0217751X9600064X. arXiv:q-alg/9510005

    1996 arXiv

  207. [220]

    EPL (Europhysics Letters) , year=

    On the R-Matrix Formulation of Deformed Algebras and Generalized Jordan-Wigner Transformations , author=. EPL (Europhysics Letters) , year=

  208. [221]

    I , author=

    Tensor algebras over Hilbert spaces. I , author=. Transactions of the American Mathematical Society , year=

  209. [222]

    Journal of the Mathematical Society of Japan , number =

    Kiyosi It. Journal of the Mathematical Society of Japan , number =. 1951 , doi =

    1951

  210. [223]

    The Homogeneous Chaos , urldate =

    Norbert Wiener , journal =. The Homogeneous Chaos , urldate =

  211. [224]

    P(0)2 Euclidean (Quantum) Field Theory , urldate =

    Barry Simon , publisher =. P(0)2 Euclidean (Quantum) Field Theory , urldate =

  212. [225]

    Mathematics of Computation , volume=

    The distribution of crossings of chords joining pairs of 2n points on a circle , author=. Mathematics of Computation , volume=

  213. [226]

    Canadian Journal of Mathematics , volume=

    Sur un probleme de configurations et sur les fractions continues , author=. Canadian Journal of Mathematics , volume=. 1952 , publisher=

    1952

  214. [227]

    letters in mathematical physics , volume=

    Generalized statistics of macroscopic fields , author=. letters in mathematical physics , volume=. 1993 , publisher=

    1993

  215. [228]

    arXiv preprint funct-an/9408002 , year=

    Completely positive maps on Coxeter groups, deformed commutation relations, and operator spaces , author=. arXiv preprint funct-an/9408002 , year=

    arXiv

  216. [229]

    SciPost Physics , volume=

    A symmetry algebra in double-scaled SYK , author=. SciPost Physics , volume=

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.