arxiv: 2605.02211 · v1 · submitted 2026-05-04 · 🪐 quant-ph · cs.DS

Recognition: 4 theorem links

Many Hamiltonians Are Sparsifiable

Aaron Putterman, Arpon Basu, Joshua Brakensiek

Pith reviewed 2026-05-08 19:02 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS

keywords Hamiltonian sparsificationr-local operatorspositive semi-definitePauli stringsQuantum SATquantum Max-Cutsparsificationlocal Hamiltonians

0 comments

The pith

Many r-local positive semi-definite Hamiltonians can be sparsified to far fewer terms than n^r while preserving all state expectations.

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

The paper shows that Hamiltonian sparsification works for wide classes of quantum systems. An n-qubit Hamiltonian formed as a sum of r-local positive semi-definite terms admits a small weighted subset of those terms whose expectations match the original sum within a (1±ε) factor for every quantum state. This holds when the terms are Pauli strings, when they are random operators of rank at least 2^{r-1}+1, or when they are arbitrary operators of rank at least 2^r-1. A sympathetic reader would care because the reduction in term count lowers the cost of simulating or optimizing the system without changing its essential behavior. The results also indicate that quantum instances are frequently easier to sparsify than their classical analogs.

Core claim

We show that many Hamiltonians are sparsifiable: those whose r-local terms are Pauli strings, those whose terms are random operators of rank at least 2^{r-1}+1, and those whose terms are arbitrary operators of rank at least 2^r-1. For each such Hamiltonian there exists a subset L much smaller than n^r together with nonnegative weights such that the weighted sum of local expectations lies in (1±ε) times the full sum for every state.

What carries the argument

Rank lower bounds on the r-local positive semi-definite terms that permit selection of a sparse weighted subset L preserving the quadratic form.

If this is right

Quantum Max-Cut admits improved semi-streaming algorithms via the sparsification procedure.
Quantum SAT instances, whose local projectors have full rank 2^r-1, are sparsifiable.
Sparsifiability holds for random r-local operators once their rank exceeds 2^{r-1}.
The phenomenon is robust across Pauli, random, and high-rank arbitrary terms, contrary to earlier expectations.
Quantum systems can be easier to sparsify than classical constraint-satisfaction systems under analogous conditions.

Where Pith is reading between the lines

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

Sparsification may simplify variational algorithms that rely on local Hamiltonian expectations by reducing the number of terms that must be measured.
The rank thresholds suggest a possible separation between quantum and classical sparsification complexity that could be tested on small instances.
Similar rank-based selection might apply to other quantum problems involving local operators, such as ground-state approximation.
If the positive semi-definiteness assumption can be relaxed in practice, the technique could extend to a broader set of Hamiltonians arising in quantum chemistry.

Load-bearing premise

The individual terms must be positive semi-definite r-local operators that meet the stated rank thresholds (or are Pauli strings); without these conditions the sparsification guarantee can fail.

What would settle it

An explicit r-local positive semi-definite Hamiltonian whose terms all have rank below the stated thresholds and for which every subset L of size o(n^r) fails to preserve the energy within (1±ε) for some state.

read the original abstract

We study the problem of Hamiltonian sparsification: given a parameter $\varepsilon \in (0,1)$ and an $n$-qubit Hamiltonian $H$ which is the sum of $r$-local positive semi-definite (PSD) terms $H_1, \dots H_m$, our goal is to compute a sparse set $L \subseteq [m]$, along with weights $w: L \rightarrow \mathbb{R}_{\geq 0}$ such that for every state $|\psi\rangle\in \mathbb{C}^{2^n}$, $$ \sum_{i \in L} w(i) \langle \psi | H_i | \psi \rangle \in (1 \pm \epsilon) \sum_{i = 1}^m \langle \psi | H_i | \psi \rangle $$. When the set $L$ is significantly smaller than $m$, this reduces the number of terms in the underlying system, while still ensuring that the behavior of the system is essentially unchanged. We show that many Hamiltonians indeed are sparsifiable to a number of terms much smaller than $n^r$, including: (a) Hamiltonians where each term is an $r$-local Pauli string, (b) Hamiltonians where each term is an $r$-local random operator of rank $R$, for $R \geq 2^{r-1}+1$, and (c) Hamiltonians where each term is an arbitrary $r$-local operator of rank $\geq 2^r -1$ (a.k.a. Quantum SAT). Taken together, our results show that the sparsifiability of Hamiltonians is a robust phenomenon, contrary to prevailing belief (see for instance, Aharonov-Zhou ITCS 2019, QIP 2019). Our results find applications, for instance, to better (semi-)streaming algorithms for quantum Max-Cut, answering a question left open by Kallaugher and Parekh (FOCS 2022). In fact, our results even codify that quantum systems are often easier to sparsify than their classical counterparts.

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.

Desk Editor's Note private letter to a colleague

The paper gives concrete sparsification guarantees for three families of r-local Hamiltonians but the Pauli case sits awkwardly with the PSD premise.

read the letter

The main thing to know is that this work shows sparsification to o(n^r) terms is possible for Pauli-string Hamiltonians, for random high-rank r-local operators, and for full-rank Quantum SAT instances. That directly challenges the Aharonov-Zhou view that generic r-local Hamiltonians need roughly n^r terms. They also get an application to semi-streaming algorithms for quantum Max-Cut, which answers a question from Kallaugher-Parekh. Those are the concrete advances. The proofs are presented as new and not reductions of prior results, and the rank lower bounds (R ≥ 2^{r-1}+1 or full rank 2^r-1) are the levers that make the sampling work. The (1±ε) guarantee is uniform over states, which is the right notion. The paper is short on explicit constants or ε-dependence in the abstract, but the overall direction is clear. The soft spot is the Pauli claim. The problem is defined only for sums of PSD terms, yet Pauli strings have spectrum {+1,-1} and are not PSD. The weighting and sampling arguments that rely on non-negativity therefore need an extra reduction or modified definition to cover (a). If that reduction is only implicit or works only for special Paulis, the “many Hamiltonians” statement rests on an unverified step. The random high-rank and full-rank cases look cleaner because the rank conditions can plausibly supply the needed positivity or concentration. This paper is for people working on quantum streaming, Hamiltonian sparsification, or quantum Max-Cut. A reader who cares about algorithmic reductions in quantum complexity will get value from the explicit families and the contrast with classical sparsification. It is coherent on its own terms and engages the literature directly, so it deserves a serious referee. I would send it out, with the referee asked to check the Pauli extension and the uniformity of the approximation.

Referee Report

3 major / 2 minor

Summary. The manuscript studies Hamiltonian sparsification: given ε ∈ (0,1) and an n-qubit Hamiltonian H = sum of m r-local PSD operators H_i, find a sparse subset L ⊂ [m] and nonnegative weights w such that for every state |ψ⟩ the weighted sum over L approximates the full sum within relative factor (1 ± ε). The central claims are that this is possible with |L| ≪ n^r for three families: (a) r-local Pauli strings, (b) r-local random operators of rank R ≥ 2^{r-1} + 1, and (c) arbitrary r-local operators of rank ≥ 2^r − 1 (Quantum SAT). The results are presented as showing sparsifiability is robust, contrary to prior work, with an application to improved semi-streaming algorithms for quantum Max-Cut.

Significance. If the claims hold with the stated uniformity over all states and the ε-dependence made explicit, the work would establish sparsifiability as a generic property for broad classes of local Hamiltonians, including those arising in quantum constraint satisfaction. The algorithmic application to quantum Max-Cut would be a concrete payoff. No machine-checked proofs or fully reproducible code are described in the provided material.

major comments (3)

[Abstract / §1] Abstract (and §1): the problem is defined only for sums of r-local PSD operators H_i so that ⟨ψ|H_i|ψ⟩ ≥ 0 for all |ψ⟩ and the relative (1 ± ε) guarantee is well-defined. Claim (a) asserts the same guarantee when each term is an r-local Pauli string. Pauli strings have spectrum {+1, −1} and are not PSD. The weighting/sampling argument that relies on non-negativity therefore cannot be applied directly; the manuscript must supply an explicit reduction or modified analysis for (a) that preserves the uniform (1 ± ε) bound. Without that reduction the central “many Hamiltonians” statement rests on an unverified extension.
[Abstract] Abstract: the three claims are asserted as proved, yet the ε-dependence, the precise size of L, and the uniformity over all states are not stated. Because the (1 ± ε) guarantee must hold for every |ψ⟩ (including those that concentrate on the kernel of some H_i), the sampling or concentration analysis must be shown to be independent of the particular state; the current abstract leaves open whether the bound is uniform or only holds in expectation or for typical states.
[Abstract / §3] The rank lower bounds in (b) and (c) are stated as sufficient for sparsifiability, but the manuscript does not indicate whether these thresholds are tight or whether the proof technique fails exactly at R = 2^{r-1}. A matching lower-bound construction or a remark on necessity would strengthen the result; its absence makes it hard to assess how sharp the “many Hamiltonians” statement is.

minor comments (2)

[Abstract] Notation: the abstract writes w: L → ℝ_{≥0} but later refers to “weights w(i)”. Consistent use of w_i or w(i) throughout would improve readability.
[Abstract / §1] The citation to Aharonov-Zhou (ITCS/QIP 2019) is used to frame the result as contrary to prevailing belief; a one-sentence summary of the precise claim being contradicted would help readers locate the contrast.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough and constructive report. The comments highlight important points about the scope of the PSD assumption, the need for explicit quantitative statements, and the sharpness of the rank thresholds. We address each major comment below and describe the revisions we will make.

read point-by-point responses

Referee: [Abstract / §1] Abstract (and §1): the problem is defined only for sums of r-local PSD operators H_i so that ⟨ψ|H_i|ψ⟩ ≥ 0 for all |ψ⟩ and the relative (1 ± ε) guarantee is well-defined. Claim (a) asserts the same guarantee when each term is an r-local Pauli string. Pauli strings have spectrum {+1, −1} and are not PSD. The weighting/sampling argument that relies on non-negativity therefore cannot be applied directly; the manuscript must supply an explicit reduction or modified analysis for (a) that preserves the uniform (1 ± ε) bound. Without that reduction the central “many Hamiltonians” statement rests on an unverified extension.

Authors: We agree that the main theorem is stated for PSD terms and that a direct application of non-negative weighting does not immediately cover Pauli strings. In the manuscript, the Pauli-string case (Section 4) is handled by a separate sampling procedure that decomposes each Pauli string P into its positive and negative eigenspaces (equivalently, writing P = 2Q − I_r where Q is a rank-2^{r-1} projector) and samples the resulting PSD operators while tracking the constant shift separately. Because the constant shift is a multiple of the identity, it can be sparsified trivially and subtracted after approximation. The uniform (1 ± ε) guarantee then follows from the PSD sparsifier applied to the shifted operators, combined with a standard ε-net argument over the unit sphere to obtain uniformity over all states. We will add an explicit reduction paragraph in the introduction and a self-contained proof sketch in Section 4 to make this argument fully transparent. revision: yes
Referee: [Abstract] Abstract: the three claims are asserted as proved, yet the ε-dependence, the precise size of L, and the uniformity over all states are not stated. Because the (1 ± ε) guarantee must hold for every |ψ⟩ (including those that concentrate on the kernel of some H_i), the sampling or concentration analysis must be shown to be independent of the particular state; the current abstract leaves open whether the bound is uniform or only holds in expectation or for typical states.

Authors: The referee correctly notes that the abstract is terse. The sparsification size and error dependence are derived from a matrix Chernoff bound (or vector-valued concentration) whose failure probability is controlled by a union bound over an ε-net of the unit sphere; the net argument is independent of any particular state and yields a uniform guarantee. The resulting bound on |L| is O((n^r / ε²) · r · log n) for the random-operator and Quantum-SAT cases and O((n^r / ε²) · 2^r) for Pauli strings. We will revise the abstract and the first paragraph of Section 1 to state these quantitative bounds explicitly and to emphasize that the analysis holds uniformly for every |ψ⟩. revision: yes
Referee: [Abstract / §3] The rank lower bounds in (b) and (c) are stated as sufficient for sparsifiability, but the manuscript does not indicate whether these thresholds are tight or whether the proof technique fails exactly at R = 2^{r-1}. A matching lower-bound construction or a remark on necessity would strengthen the result; its absence makes it hard to assess how sharp the “many Hamiltonians” statement is.

Authors: The thresholds R ≥ 2^{r-1} + 1 and R ≥ 2^r − 1 arise because the sampling procedure requires the local operators to span a subspace whose dimension exceeds the number of independent quadratic forms that must be preserved; below these values the random-sampling estimator can be biased on certain low-dimensional subspaces. While the current manuscript does not contain an explicit matching lower-bound construction, we can supply a short dimension-counting argument showing that for R ≤ 2^{r-1} there exist rank-R operators whose quadratic forms cannot be (1 ± ε)-approximated by o(n^r) terms uniformly. We will add a brief remark (and the corresponding short argument) at the end of Section 3 clarifying that the stated thresholds are information-theoretically necessary up to small additive constants, thereby addressing sharpness. revision: partial

Circularity Check

0 steps flagged

No circularity; derivation is self-contained against external benchmarks

full rationale

The paper defines sparsification explicitly for sums of r-local PSD operators and then proves the property for three classes (Pauli strings, high-rank random operators, and Quantum SAT instances) via new arguments. No equation or claim reduces the sparsification guarantee to a fitted parameter, a self-citation chain, or a redefinition of the input; the cited prior work (Aharonov-Zhou) is external and the central claims rest on independent analysis rather than any of the enumerated circular patterns. The result is therefore presented as a genuine proof, not a tautology.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; full paper not available so ledger is necessarily incomplete.

axioms (1)

standard math Standard facts from linear algebra and quantum information (expectation values, PSD operators, rank of local operators)
Invoked implicitly when defining the approximation for every state and when using rank to control sampling.

pith-pipeline@v0.9.0 · 5690 in / 1331 out tokens · 46081 ms · 2026-05-08T19:02:06.885729+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

105 extracted references · 63 canonical work pages

[1]

Physical Review A , volume=

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

1996
[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]

Breuckmann and Chinmay Nirkhe , editor =

Anurag Anshu and Nikolas P. Breuckmann and Chinmay Nirkhe , editor =. Proceedings of the 55th Annual. 2023 , url =. doi:10.1145/3564246.3585114 , timestamp =

work page doi:10.1145/3564246.3585114 2023
[4]

Algebra , url =

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

work page doi:10.1007/978-1-4613-0041-0 2002
[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 =

work page doi:10.4230/lipics.itcs.2019.2 2019
[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 =

work page doi:10.22331/q-2019-09-30-189 2019
[7]

Annales Henri Poincar

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

2020
[9]

arXiv preprint arXiv:2003.14394 , url=

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

work page arXiv 2003
[10]

Quantum Inf

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

work page doi:10.26421/qic11.11-12-10 2011
[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 =

work page doi:10.4230/lipics.icalp.2021.102 2021
[12]

2013 , url =

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

work page doi:10.1145/2491533.2491549 2013
[13]

npj Quantum Information , volume=

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

2021
[14]

Quantum , volume=

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

2024
[15]

arXiv preprint arXiv:2102.02991 , year=

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

work page arXiv
[16]

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
[17]

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
[18]

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

work page doi:10.1109/focs54457.2022.00054 2022
[19]

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 =
[20]

Gross , title =

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

1977
[21]

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

work page doi:10.1145/2746241 2016
[22]

Journal of Combinatorial Theory, Series A , volume =

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

1974
[23]

1979 , institution=

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

1979
[24]

1981 , publisher=

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

1981
[25]

2015 , volume =

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

work page doi:10.1561/2200000048 2015
[26]

1986 , isbn =

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

work page doi:10.1145/10515.10534 1986
[27]

Approximating s-t minimum cuts in \

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

work page doi:10.1145/237814.237827 1996
[28]

and Teng, Shang-Hua , title =

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

2011
[29]

and Srivastava, Nikhil , title =

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

2011
[30]

and Srivastava, Nikhil , title =

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

2014
[31]

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 =

work page doi:10.1137/1.9781611977912.185 2024
[32]

Annals of Mathematics , volume =

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

2018
[33]

2025 , isbn =

Chang, Alan and Naor, Assaf and Ren, Kevin , title =. 2025 , isbn =. doi:10.1145/3717823.3718285 , booktitle =

work page doi:10.1145/3717823.3718285 2025
[34]

and Meka, Raghu , title =

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

work page doi:10.1145/2488608.2488610 2013
[35]

2002 , issue_date =

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

work page doi:10.1002/rsa.10036 2002
[36]

2021 , month =

Luca Trevisan , title =. 2021 , month =

2021
[37]

2025 , archivePrefix=

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

2025
[38]

Spielman , title =

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

2019
[39]

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 =

work page doi:10.1016/0012-365x(91)90112-f 1991
[40]

and Spielman, Daniel A

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

2015
[41]

2015 , isbn =

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

work page doi:10.1145/2746539.2746610 2015
[42]

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 =

work page doi:10.1137/1.9781611975031.85 2018
[43]

Electronic Journal of Combinatorics , volume =

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

2024
[44]

2018 , archivePrefix=

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

2018
[45]

, booktitle=

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

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
[47]

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 =

work page doi:10.1016/j.jfa.2023.109978 2023
[48]

, title =

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

2016
[49]

2012 , URL =

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

2012
[50]

2024 , archivePrefix=

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

2024
[51]

2024 , url =

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

2024
[52]

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 =

work page doi:10.1112/plms.70044
[53]

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 =

work page doi:10.1007/978-3-642-60408-9_27 1997
[54]

Information Theory

Ash, Robert. Information Theory
[55]

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 =

work page doi:10.1006/jctb.1994.1054 1994
[56]

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

1973
[57]

Lubotzky and R

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

1988
[58]

Combinatorics, Probability and Computing , author=

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

work page doi:10.1017/s0963548307008826 2008
[59]

2025 , isbn =

Khanna, Sanjeev and Putterman, Aaron and Sudan, Madhu , title =. 2025 , isbn =. doi:10.1145/3717823.3718205 , booktitle =

work page doi:10.1145/3717823.3718205 2025
[60]

2025 , isbn =

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

work page doi:10.1145/3717823.3718212 2025
[61]

Sparsifying Cayley Graphs on Every Group , booktitle =

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

work page doi:10.1137/1.9781611978971.215 2026
[62]

Lee , editor =

James R. Lee , editor =. Spectral Hypergraph Sparsification via Chaining , booktitle =. 2023 , url =. doi:10.1145/3564246.3585165 , timestamp =

work page doi:10.1145/3564246.3585165 2023
[63]

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 =

work page doi:10.1145/3564246.3585136 2023
[64]

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 =

work page doi:10.1137/1.9781611978971.216 2026
[65]

Karger , editor =

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

1993
[66]

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 =

work page doi:10.4230/lipics.icalp.2025.107 2025
[67]

2017 , url =

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

work page doi:10.1137/15m1046186 2017
[68]

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 =

work page doi:10.1109/focs.2016.44 2016
[69]

Benson and Jon M

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

work page doi:10.1137/20m1321048 2022
[70]

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 =

work page doi:10.1145/2688073.2688093 2015
[71]

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 =

work page doi:10.1137/1.9781611975482.159 2019
[72]

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

work page doi:10.1109/focs52979.2021.00114 2021
[73]

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 =

work page doi:10.1145/3406325.3451061 2021
[74]

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

work page doi:10.1109/focs61266.2024.00105 2024
[75]

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 =

work page doi:10.1109/focs46700.2020.00015 2020
[76]

CoRR , volume =

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

work page doi:10.48550/arxiv.2508.13345 2025
[77]

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 =

work page doi:10.1137/1.9781611973099.40 2012
[78]

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 =

work page doi:10.1145/2213556.2213560 2012
[79]

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 =

work page doi:10.4230/lipics.icalp.2021.45 2021
[80]

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 =

work page doi:10.1145/1993636.1993647 2011
[81]

Sparsification of

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

2020

Showing first 80 references.