pith. sign in

arxiv: 2606.09728 · v1 · pith:ICL5JJFRnew · submitted 2026-06-08 · 🪐 quant-ph · cs.DS

Quantum Cut Sparsifiers

Arpon Basu , Joshua Brakensiek , Pravesh K. Kothari , Aaron Putterman This is my paper

Pith reviewed 2026-06-27 16:33 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS
keywords quantum cut hamiltonianssparsificationkikuchi graphsoperator inequalitiesexpander decompositionimportance samplingquantum hamiltonians
0
0 comments X

The pith

Any n-qubit Quantum Cut Hamiltonian sparsifies to Õ(n/ε²) terms while preserving the energy of every state up to 1 ± ε.

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

The paper shows that any Quantum Cut Hamiltonian on n qubits reduces to roughly n over epsilon squared terms such that the energy of every quantum state remains within a multiplicative 1 ± ε factor of the original. This sparsification comes from an importance sampling of the edges of the underlying graph that makes the Kikuchi graph at every level spectrally close to the original, using the same sample for all levels. The method decomposes the relevant matrices into invariant subspaces to apply an operator-valued inequality that produces the uniform sampling, then invokes expander decomposition to cover arbitrary graphs.

Core claim

In an n-qubit system, any n-qubit QC Hamiltonian can be sparsified to Õ(n /ε²) many terms while preserving the energy of every state up to a factor of 1 ± ε. This gives an importance sampling scheme for the edges of an arbitrary graph G such that the Kikuchi graph at level ℓ of the sampled graph is a spectral approximation to the Kikuchi graph of G, with the same sampling working simultaneously for all ℓ.

What carries the argument

Invariant subspace decomposition of the matrices, which lets the Alon-Kozma operator-valued inequality produce a uniform edge sampling that simultaneously approximates the Kikuchi graph at every level.

If this is right

  • The sparsifier for expander graphs extends to arbitrary graphs via expander decomposition.
  • A single sampling scheme approximates the Kikuchi graph at every level ℓ simultaneously.
  • QC Hamiltonian energies can be approximated using far fewer terms than the original while controlling error for all states.

Where Pith is reading between the lines

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

  • The result may allow more efficient classical algorithms for approximating energies or ground states in QC models by reducing term count.
  • Similar subspace-based sampling could apply to other quantum Hamiltonians where invariant decompositions are available.
  • The bound suggests a quantum analogue of classical cut sparsifiers, with tightness testable on small explicit QC Hamiltonians.

Load-bearing premise

Decomposing the matrices into invariant subspaces is sufficient for the Alon-Kozma operator-valued inequality to yield a uniform sampling scheme that works simultaneously for every level ℓ of the Kikuchi graph.

What would settle it

An n-qubit QC Hamiltonian for which every sparsifier with o(n/ε²) terms fails to keep the energy of some state inside the 1 ± ε factor, or for which no single sampling approximates all Kikuchi levels at once.

read the original abstract

In this paper, we continue a line of research initiated by Basu, Brakensiek, and Putterman [2026] studying the sparsifiability of Hamiltonians. We focus particularly on the sparsifiability of the widely-studied Quantum Cut (QC) Hamiltonians. Our main result is that in an $n$-qubit system, any $n$-qubit QC Hamiltonian can be sparsified to $\widetilde{O}(n /\varepsilon^2)$ many terms while preserving the energy of every state up to a factor of $1 \pm \varepsilon$. Our result can be interpreted as giving an importance sampling scheme for the edges of an arbitrary graph $G$ such that the \emph{Kikuchi} graph at level $\ell$ of the sampled graph is a spectral approximation to the Kikuchi graph of $G$. Importantly, the \emph{same} sampling scheme works simultaneously for all $\ell$. The natural approach of leverage score sampling, analyzed via matrix concentration inequalities, yields a polynomially worse bound in our setting because the underlying matrices have dimension $\sim 2^n$. Instead, our approach relies on decomposing the action of these matrices into invariant subspaces. Then, by using an operator-valued inequality of Alon and Kozma [Ann. Henri Poincar\'e, 2020], itself building on an \emph{octopus inequality} of Caputo, Liggett, and Richthammer [J. AMS, 2010], we extend our sparsification technique to all expander graphs. We then invoke expander decomposition to extend our sparsifier to all graphs.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The paper claims that any n-qubit Quantum Cut (QC) Hamiltonian can be sparsified to ilde{O}(n/\varepsilon^2) terms while preserving the energy of every state up to a (1 \pm \varepsilon) factor. This is realized by an importance-sampling scheme on the edges of an arbitrary graph G such that the induced Kikuchi graph at every level \ell is a spectral approximation to the original, with the identical sampling distribution working simultaneously for all \ell. The proof proceeds by decomposing the relevant operators into invariant subspaces, applying the Alon-Kozma operator-valued inequality (itself based on the Caputo-Liggett-Richthammer octopus inequality), extending the technique to expander graphs, and finally invoking expander decomposition to handle arbitrary graphs.

Significance. If the result holds, it supplies a near-linear-size sparsifier for QC Hamiltonians that overcomes the exponential dimension barrier faced by standard matrix-concentration methods. The explicit use of invariant-subspace decomposition together with the Alon-Kozma inequality to obtain an \ell-uniform sampling scheme is a technically interesting route that may be useful in other high-dimensional quantum sparsification settings. The paper appropriately credits the external inequalities and the prior Basu-Brakensiek-Putterman line of work.

major comments (2)
  1. [Abstract (approach paragraph)] Abstract, paragraph on the approach: the claim that the invariant-subspace decomposition yields a single sampling distribution whose induced Kikuchi graphs are spectral approximations at every level \ell simultaneously is load-bearing for the main theorem, yet the manuscript does not exhibit that the variance proxies or operator-norm bounds inside the Alon-Kozma inequality remain independent of the particular subspaces that arise at each \ell. If these quantities acquire an \ell-dependent factor, the resulting sampling weights would also depend on \ell, contradicting the uniform guarantee.
  2. [Section describing the expander-decomposition step] The extension via expander decomposition (final step of the argument): it is not shown that the decomposition into expanders preserves the QC Hamiltonian structure or that the energy-preservation factor (1 \pm \varepsilon) carries through the decomposition without an additional logarithmic loss that would affect the ilde{O}(n/\varepsilon^2) bound.
minor comments (2)
  1. [Abstract] The abstract refers to 'QC Hamiltonians' without a self-contained definition; a one-sentence reminder of the precise form (sum of cut terms on the underlying graph) would improve readability.
  2. [Introduction / preliminaries] Notation for the Kikuchi graph at level \ell is introduced without an explicit reference to its adjacency operator; adding a short equation or pointer to the standard definition would clarify the spectral-approximation claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment of the result's significance and for the careful reading. We address the two major comments below. Both points identify places where the manuscript's exposition can be strengthened with additional lemmas or details; we will incorporate these clarifications in the revision.

read point-by-point responses

  1. Referee: [Abstract (approach paragraph)] Abstract, paragraph on the approach: the claim that the invariant-subspace decomposition yields a single sampling distribution whose induced Kikuchi graphs are spectral approximations at every level ℓ simultaneously is load-bearing for the main theorem, yet the manuscript does not exhibit that the variance proxies or operator-norm bounds inside the Alon-Kozma inequality remain independent of the particular subspaces that arise at each ℓ. If these quantities acquire an ℓ-dependent factor, the resulting sampling weights would also depend on ℓ, contradicting the uniform guarantee.

    Authors: The referee correctly identifies that uniformity across ℓ is central. In Section 3 the invariant subspaces are the common eigenspaces of the family of Kikuchi operators; because the QC Hamiltonian is a sum of two-qubit terms, these subspaces coincide with the weight-ℓ subspaces of the n-qubit space and are therefore independent of the particular graph. The operator-norm bounds supplied to Alon-Kozma are controlled by the maximum degree of G, which is manifestly ℓ-independent. The variance proxies are likewise bounded by the squared ℓ-norm of the edge indicators, again independent of ℓ. We will add an explicit short lemma (new Lemma 3.4) stating these facts and verifying that the sampling distribution produced by the inequality is therefore the same for every ℓ. revision: yes

  2. Referee: [Section describing the expander-decomposition step] The extension via expander decomposition (final step of the argument): it is not shown that the decomposition into expanders preserves the QC Hamiltonian structure or that the energy-preservation factor (1 ± ε) carries through the decomposition without an additional logarithmic loss that would affect the ᵏ(n/ε^{2}) bound.

    Authors: The underlying graph decomposition is performed on the support graph G before any sampling; each expander component inherits the same two-qubit interaction structure, so the resulting Hamiltonians remain QC. The (1 ± ε) guarantee is multiplicative. Because the same sampling distribution is used on every component and the number of components in a standard expander decomposition is O(log n), a union bound over components contributes only an extra log n factor inside the ᵏ notation; the leading n/ε^{2} term is unaffected. The current sketch in Section 4 is too terse on error propagation. We will expand the section with a short paragraph and a reference to the standard decomposition lemma (e.g., Spielman-Teng) to make the preservation and the absence of an extra non-tilde logarithmic loss explicit. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to prior work by subset of authors; derivation relies on external inequalities

full rationale

The paper continues prior work by three of the four authors but invokes the Alon-Kozma operator-valued inequality (external, 2020), the Caputo-Liggett-Richthammer octopus inequality (external), and expander decomposition as the load-bearing tools for obtaining a single sampling distribution that works uniformly across all Kikuchi levels ℓ. No equation or claim in the provided text reduces the Õ(n/ε²) bound or the simultaneous approximation guarantee to a fitted parameter, a self-defined quantity, or a self-citation chain. The invariant-subspace decomposition is presented as enabling the application of the external inequality rather than as a tautological re-statement of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The result rests on standard mathematical tools rather than new postulates; no free parameters or invented entities are introduced in the abstract.

axioms (3)
  • standard math Operator-valued inequality of Alon and Kozma (Ann. Henri Poincaré, 2020)
    Invoked to extend the sparsification from subspaces to expander graphs.
  • standard math Octopus inequality of Caputo, Liggett, and Richthammer (J. AMS, 2010)
    Underlying the Alon-Kozma inequality used in the proof.
  • standard math Expander decomposition theorem for graphs
    Used to lift the expander case to arbitrary graphs.

pith-pipeline@v0.9.1-grok · 5829 in / 1454 out tokens · 29038 ms · 2026-06-27T16:33:05.731884+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

157 extracted references · 78 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. [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. [4]

    2002 , PAGES =

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

    Annales Henri Poincar

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

    2020

  8. [9]

    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

  9. [10]

    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

  10. [11]

    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

  11. [12]

    npj Quantum Information , volume=

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

    2021

  12. [13]

    Quantum , volume=

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

    2024

  13. [14]

    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. [15]

    arXiv preprint arXiv:2603.24530 , year=

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

    arXiv

  15. [16]

    arXiv preprint arXiv:2004.08432 , year=

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

    arXiv 2004

  16. [17]

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

    arXiv preprint arXiv:2102.02991 , year=

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

    arXiv

  18. [19]

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

    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. [21]

    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

  21. [22]

    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. [23]

    Gross , title =

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

    1977

  23. [24]

    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

  24. [25]

    Journal of Combinatorial Theory, Series A , volume =

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

    1974

  25. [26]

    1979 , institution=

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

    1979

  26. [27]

    1981 , publisher=

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

    1981

  27. [28]

    2015 , volume =

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

    work page doi:10.1561/2200000048 2015

  28. [29]

    1986 , isbn =

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

    work page doi:10.1145/10515.10534 1986

  29. [30]

    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

  30. [31]

    and Teng, Shang-Hua , title =

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

    2011

  31. [32]

    and Srivastava, Nikhil , title =

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

    2011

  32. [33]

    and Srivastava, Nikhil , title =

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

    2014

  33. [34]

    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

  34. [35]

    Annals of Mathematics , volume =

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

    2018

  35. [36]

    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

  36. [37]

    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

  37. [38]

    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

  38. [39]

    2021 , month =

    Luca Trevisan , title =. 2021 , month =

    2021

  39. [40]

    2025 , archivePrefix=

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

    2025

  40. [41]

    Spielman , title =

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

    2019

  41. [42]

    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

  42. [43]

    and Spielman, Daniel A

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

    2015

  43. [44]

    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

  44. [45]

    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

  45. [46]

    Electronic Journal of Combinatorics , volume =

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

    2024

  46. [47]

    2018 , archivePrefix=

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

    2018

  47. [48]

    , booktitle=

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

  48. [49]

    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

  49. [50]

    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

  50. [51]

    , title =

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

    2016

  51. [52]

    2012 , URL =

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

    2012

  52. [53]

    2024 , archivePrefix=

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

    2024

  53. [54]

    2024 , url =

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

    2024

  54. [55]

    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

  55. [56]

    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

  56. [57]

    Information Theory

    Ash, Robert. Information Theory

  57. [58]

    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

  58. [59]

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

    1973

  59. [60]

    Lubotzky and R

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

    1988

  60. [61]

    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

  61. [62]

    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

  62. [63]

    2025 , isbn =

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

    work page doi:10.1145/3717823.3718212 2025

  63. [64]

    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

  64. [65]

    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

  65. [66]

    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

  66. [67]

    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

  67. [68]

    Karger , editor =

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

    1993

  68. [69]

    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

  69. [70]

    2017 , url =

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

    work page doi:10.1137/15m1046186 2017

  70. [71]

    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

  71. [72]

    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

  72. [73]

    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

  73. [74]

    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

  74. [75]

    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

  75. [76]

    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

  76. [77]

    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

  77. [78]

    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

  78. [79]

    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

  79. [80]

    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

  80. [81]

    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

Showing first 80 references.