Pith. sign in

REVIEW 3 major objections 5 minor 53 references

Quantum Speedup for Hypergraph Sparsification

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read A quantum algorithm builds ε-spectral sparsifiers of weighted hypergraphs in sublinear time.

desk verdict First quantum hypergraph sparsification algorithm, but the overestimate proof assumes every hyperedge keeps a star edge in an O(n)-edge sparsifier—impossible for m >> n—so the main theorem is unsupported where the speedup is claimed. read the letter →

arxiv 2505.01763 v1 pith:6ASBKTJT submitted 2025-05-03 quant-ph cs.DS

Chenghua Liu , Minbo Gao , Zhengfeng Ji , Mingsheng Ying This is my paper · ORCID
classification quant-phcs.DS
keywords quantumalgorithmhypergraphsparsificationspectralsparsifierleveragescoreoverestimateeffectiveresistancespeedupmincutsublineartime
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

This paper claims that the open problem of quantum speedup for hypergraph sparsification has a positive answer: there is a quantum algorithm that, from query access to a weighted hypergraph with $n$ vertices, $m$ hyperedges and rank $r$, outputs an $\varepsilon$-spectral sparsifier of near-linear size in time $\widetilde O(r\sqrt{mn}/\varepsilon + r\sqrt{mnr})$. The running time is sublinear in $m$ on dense hypergraphs, and for constant rank it matches the quantum lower bound while improving on the $\widetilde O(mr)$ classical state of the art. That matters because hypergraph sparsifiers are a preprocessing step for cut, clustering, and machine-learning tasks, and a sublinear construction makes those tasks faster on dense data. The paper also derives quantum speedups for hypergraph cut sparsification and for approximating hypergraph mincut and $s$-$t$ mincut.

What carries the argument

The key machinery is the hyperedge leverage score overestimate $z$, adapted from group leverage score overestimates, together with a sparse underlying graph construction that replaces each hyperedge $e$ by a star centered at a fixed vertex $a_e$. In each of $T=O(\log r)$ rounds the algorithm sparsifies the current weighted underlying graph to $\widetilde O(n)$ edges with a quantum graph sparsifier, computes approximate effective resistances, and updates each star edge's weight to $c'_{e,f}=c_{e,f}R_f w_e/\sum_{g\in S_e}c_{e,g}R_g$, where $S_e$ is the set of star edges of $e$. A data structure stores the averaged history of these updates as a query oracle for $z$; quantum sampling through many-copies state preparation and quantum sum estimation then produce the sampled, reweighted sparsifier. The correctness analysis uses a chaining bound that controls the maximum energy deviation over all unit vectors.

What would settle it

Run Algorithm 1 on a dense rank-3 hypergraph with $m\gg n$ and record, round by round, whether each hyperedge's star edges survive the graph sparsification step; if any hyperedge is dropped in a round, the weight update that defines the next underlying graph is undefined and the overestimate claim cannot hold as stated.

Watch

Extended reading notes

Core claim

The central discovery is a quantum algorithm (Theorem 4.1) that produces an $\varepsilon$-spectral sparsifier of a weighted hypergraph $H$ with $O(n\log n\log r/\varepsilon^2)$ hyperedges, with high probability, in time $\widetilde O(r\sqrt{mnr} + r\sqrt{mn}/\varepsilon)$. When the hypergraph is dense ($m\ge nr$) and $\varepsilon\ge\sqrt{n/m}$, the time simplifies to $\widetilde O(r\sqrt{mn}/\varepsilon)$, which is sublinear in $m$. The algorithm works by computing a vector $z$ of hyperedge leverage score overestimates — entrywise upper bounds on hyperedge leverage scores with total sum $O(n)$ — and then sampling $\widetilde O(n\log n\log r/\varepsilon^2)$ hyperedges with probability proportional to $z$, reweighting each sampled edge by the ratio of its original weight to the sampling probability. The overestimates are produced by a quantum iterative procedure that sparsifies a sequence of sparse underlying graphs and queries their effective resistances, and the sampling is done without ever forming the full vector $z$ explicitly.

Load-bearing premise

The proof that $z$ is an overestimate assumes that, in every one of the $T$ rounds, the $\widetilde O(n)$-edge sparsified graph $\tilde G(t)$ keeps at least one star edge from every hyperedge $e$, so the weight update defining $c'_{e,f}$ has a nonzero denominator; this is not shown and can fail when $m$ is much larger than $n$.

Editorial extensions

If this is right

  • For constant rank $r$, the $\widetilde O(\sqrt{mn}/\varepsilon)$ time matches the quantum lower bound and is sublinear in $m$, answering the previously open problem on quantum hypergraph sparsification.
  • On dense hypergraphs ($m=\Omega(nr)$), the algorithm runs in roughly $r n^{(r+1)/2}$ time against roughly $r n^r$ classically, a near-quadratic separation in $n$.
  • The same construction, restricted to indicator vectors, is an $\varepsilon$-cut sparsifier, yielding quantum algorithms for $(1+\varepsilon)$-approximate hypergraph mincut and $s$-$t$ mincut in sublinear time with respect to $m$.
  • The output has $O(n\log n\log r/\varepsilon^2)$ hyperedges, matching the best classical sparsifier size, so the speedup does not sacrifice the approximation guarantee.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the hidden survival assumption is repaired, the same overestimate-and-sample template could plausibly be ported to directed hypergraph sparsification and generalized-linear-model sparsification, whose classical algorithms use the same group-leverage-score structure.
  • The advertised time assumes quantum-read classical-write random access memory (QRAM); without QRAM the speedup is not expected to survive, so the practical impact is tied to QRAM hardware.
  • One concrete way to stress-test the claim is to instrument the algorithm on random dense hypergraphs and measure how often a hyperedge loses all its star edges; even one such round would invalidate the current proof, while showing the assumption holds empirically would strengthen confidence in the result.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper proposes the first quantum algorithm for hypergraph spectral sparsification. Given query access to a weighted hypergraph H with n vertices, m hyperedges, and rank r, and accuracy ε, the algorithm outputs an ε-spectral sparsifier with O(n log n log r / ε²) hyperedges in time ~O(r√(mn)/ε + r√(mnr)). The approach adapts the classical framework of Jambulapati et al. (2023) and Lee (2023): it iteratively constructs sparse underlying graphs using quantum graph sparsification (Apers–de Wolf), computes approximate effective resistances quantumly, builds a hyperedge leverage score overestimate, then samples hyperedges via quantum state preparation and uses quantum sum estimation for reweighting. The correctness proof relies on a chaining argument from Lee (2023). The claimed result matches the quantum lower bound of Apers–de Wolf for constant r and improves on classical ~O(mr) algorithms for dense hypergraphs.

Significance. If correct, this would resolve an open problem of Apers and de Wolf and give the first quantum speedup for hypergraph sparsification, with applications to cut sparsifiers and mincut problems. The paper combines several sophisticated external quantum primitives (quantum graph sparsification, multi-sampling, sum estimation) with a nontrivial chaining analysis, and it clearly states the parameter regime in which the speedup occurs. However, the core correctness proof of the leverage-score overestimate step (Proposition B.7) contains a load-bearing gap that breaks precisely in the dense regime where the speedup is claimed; as a result, the central theorem is not supported.

major comments (3)
  1. [Appendix B, Proposition B.7] The proof fixes, for each hyperedge e, a star edge f* ∈ S_e that maximizes R_f in the original underlying graph and then applies the weight-update formula (Eq. (7)) to ~c^{(t)}_{e,f*} for every round t. However, Eq. (7) is only evaluated for edges present in the stored sparsifier ~G(t), which has ~O(n/α1²) edges. The proof gives no argument that f* survives in ~G(t) for all t, and in the dense regime m = Ω(nr) such an argument cannot hold: the sparsifier can contain at most O(n) edges, while there are m ≫ n hyperedges, each requiring at least one distinct star edge to be covered. For a rank-3 hypergraph with m = Θ(n²) and pairwise nearly disjoint star sets, most hyperedges have no surviving star edge in any round; for these e, the algorithm computes z_e = 0, violating the required z_e ≥ w_e R_e. Thus inequality (d) of Proposition B.7 and the subsequent telescoping conclusion are invalid for exactly the parameter regime that gives the quantum speedup.
  2. [Appendix C, chaining bound] The bound ||A||_{2→∞} ≤ √~s used in Eq. (11) relies on the overestimate condition z_e ≥ w_e R_e for every hyperedge e. As argued above, this condition fails in the dense regime, so the application of Lemma C.1 is unsupported and the final expectation bound τ ≤ ε does not follow. The proof of Theorem 4.1 is therefore incomplete even if one were to grant the rest of the chaining argument.
  3. [Algorithm 1, line 6] WeightCompute queries the stored sparsifier ~G(t); when a hyperedge has no surviving star edge in ~G(t), the denominator sum_{g∈S_e} ~c^{(t)}_{e,g} ~R^{(t)}_g is zero and the update in Eq. (7) is undefined (or yields zero). The algorithm does not specify how such hyperedges are handled, and the proof of Theorem 3.4 does not address them. This makes the failure of Proposition B.7 an algorithmic issue, not merely a proof-technical one.
minor comments (5)
  1. [Introduction, first paragraph] The word 'garph sparsification' should read 'graph sparsification'.
  2. [Definition 3.3] The notation F = {(e,f) : f ∈ S_e, e ∈ E} is confusing because it overloads e; consider writing (h,f) with h ∈ E to distinguish the hyperedge from the fixed vertex.
  3. [Proof of Theorem 4.1, Appendix C] The sentence 'lim_{v→1} Q_H(v) = 0' is unclear; it should specify that v approaches the all-ones vector and explain why this justifies the subsequent simplification of the max term.
  4. [Appendix B, Proposition B.3] The construction of U'_{Z_G} using O(q) queries to U_{Z_G} is only sketched; the tensor-product structure of the constructed register is not fully defined.
  5. [General notation] The tilde notation for sparsifier edges (~F(t)) and effective resistances (~R^{(t)}) is occasionally inconsistent; for example, in Proposition B.7 both ~R^{(t)}_f and R^{(t)}_f appear without a clear convention.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is built from independent external theorems and analytically chosen constants, with no fitted parameter renamed as a prediction.

full rationale

The derivation chain is self-contained with respect to external, peer-reviewed results. Theorem 4.1 invokes Theorem 2.6 (quantum graph sparsification from Apers & de Wolf), Corollary 2.8 (Hamoudi's many-copy quantum state preparation), Theorem 2.9 (quantum sum estimation from Li et al.), and Lemma C.1 (Lee's chaining bound). None of these citations is authored by the present paper's authors, and none encodes the target hypergraph result as an input. The overestimate computation in Proposition B.7 is a standard multiplicative-weights loop: Eq. (7) is an explicit update rule, and the proof that z_e >= w_e R_e uses convexity of log effective resistance and a telescoping sum, so the desired inequality is proved rather than assumed. The sampling step uses z as importance weights and proves an expected-error bound via independent symmetrization and chaining; the sparsifier size M is chosen analytically as Theta(n log n log r / epsilon^2). There is no parameter fitted to a subset of data and then relabeled as a prediction, and no uniqueness theorem is imported from same-author work. The potential concern that Proposition B.7 assumes every hyperedge retains a star edge in the O(n)-edge graph sparsifier is, if valid, a correctness gap in the dense regime rather than a circularity: it does not reduce any claimed output to an input by construction.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new physical entities. The central proof relies on the quantum graph sparsification primitive, the many-copy state preparation primitive, the quantum sum estimation primitive, and Lee's chaining bound. The main unstated assumption is the survival of at least one star edge per hyperedge through every graph sparsification round, which is load-bearing and not justified. The algorithm constants alpha1, alpha2, and T are arbitrary and not fitted to data.

free parameters (3)
  • alpha1 = 0.1
    Chosen constant in Algorithm 1; any small positive constant would work, so it is not fitted to data.
  • alpha2 = 0.1
    Chosen approximation factor for effective resistance; arbitrary small positive constant, not fitted.
  • T = log(r-1)
    Number of rounds in the overestimate loop; chosen to make the telescoping bound have a log r factor.
assumptions (5)
  • domain assumption The quantum graph sparsification subroutine from Apers and de Wolf works with the implicit edge-vertex incidence oracle provided by UG(t) and returns a reweighted subgraph with O(n/epsilon^2) edges.
    Used in Algorithm 1 line 3. The paper does not explicitly construct the O_vtx oracle for the labeled edge set (e,f) of the sparse underlying graph.
  • ad hoc to paper Every hyperedge retains at least one star edge in every graph sparsifier \tilde G(t), so that Eq. (7) is well-defined and z_e is positive.
    Needed for Proposition B.7 but never proved. It is false when m is much larger than n because the sparsifier has only O(n) edges.
  • standard math Lee's chaining bound, Lemma C.1, applies to the sampled hyperedge set with the stated values of s, n, and D.
    Used in the proof of Theorem 4.1 as an external theorem.
  • domain assumption QRAM and the quantum oracles OH and Ow are available at unit cost.
    Standard in quantum query algorithms; the paper notes that QRAM is speculative with current hardware.
  • domain assumption The approximation parameter satisfies epsilon >= sqrt(n/m), so the output sparsifier is no larger than the input.
    Used in Remark 4.2 and required by the quantum graph sparsification theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Speedup for Hypergraph Sparsification." pith.science (2026). https://pith.science/paper/6ASBKTJT

@misc{pith2026250501763,
  author       = {Pith},
  title        = {Pith review of: Quantum Speedup for Hypergraph Sparsification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6ASBKTJT}},
  note         = {Machine review of arXiv:2505.01763}
}
abstract

Graph sparsification serves as a foundation for many algorithms, such as approximation algorithms for graph cuts and Laplacian system solvers. As its natural generalization, hypergraph sparsification has recently gained increasing attention, with broad applications in graph machine learning and other areas. In this work, we propose the first quantum algorithm for hypergraph sparsification, addressing an open problem proposed by Apers and de Wolf (FOCS'20). For a weighted hypergraph with $n$ vertices, $m$ hyperedges, and rank $r$, our algorithm outputs a near-linear size $\varepsilon$-spectral sparsifier in time $\widetilde O(r\sqrt{mn}/\varepsilon)$. This algorithm matches the quantum lower bound for constant $r$ and demonstrates quantum speedup when compared with the state-of-the-art $\widetilde O(mr)$-time classical algorithm. As applications, our algorithm implies quantum speedups for computing hypergraph cut sparsifiers, approximating hypergraph mincuts and hypergraph $s$-$t$ mincuts.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 23 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Sublinear algorithms for hierarchical clustering

    Agarwal, A., Khanna, S., Li, H., and Patil, P. Sublinear algorithms for hierarchical clustering. Advances in Neural Information Processing Systems, 35: 0 3417--3430, 2022

    work page 2022

  3. [3]

    Hypergraph partitioning based models and methods for exploiting cache locality in sparse matrix-vector multiplication

    Akbudak, K., Kayaaslan, E., and Aykanat, C. Hypergraph partitioning based models and methods for exploiting cache locality in sparse matrix-vector multiplication. SIAM Journal on Scientific Computing, 35 0 (3): 0 C237--C262, 2013. doi:10.1137/100813956

    work page doi:10.1137/100813956 2013

  4. [4]

    Alpert, C. J. and Kahng, A. B. Recent directions in netlist partitioning: a survey. Integration, 19 0 (1): 0 1--81, 1995. ISSN 0167-9260. doi:https://doi.org/10.1016/0167-9260(95)00008-4

    doi:10.1016/0167-9260(95)00008-4 1995

  5. [6]

    and Gribling, S

    Apers, S. and Gribling, S. Quantum speedups for linear programming via interior point methods, 2024. URL https://arxiv.org/abs/2311.03215

    arXiv 2024

  6. [7]

    and Lee, T

    Apers, S. and Lee, T. Quantum complexity of minimum cut. In Proceedings of the 36th Computational Complexity Conference, 2021. doi:10.4230/LIPIcs.CCC.2021.28

    work page doi:10.4230/lipics.ccc.2021.28 2021

  7. [8]

    A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs, 2024

    Apers, S., Auza, A., and Lee, T. A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs, 2024. URL https://arxiv.org/abs/2110.15587

    arXiv 2024

  8. [9]

    Hypergraph partitioning for sparse matrix-matrix multiplication

    Ballard, G., Druinsky, A., Knight, N., and Schwartz, O. Hypergraph partitioning for sparse matrix-matrix multiplication. ACM Trans. Parallel Comput., 3 0 (3), December 2016. ISSN 2329-4949. doi:10.1145/3015144

    doi:10.1145/3015144 2016

Show all 53 references
  1. [10]

    New notions and constructions of sparsification for graphs and hypergraphs

    Bansal, N., Svensson, O., and Trevisan, L. New notions and constructions of sparsification for graphs and hypergraphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, pp.\ 910--928, 2019. doi:10.1109/FOCS.2019.00059

    2019

  2. [11]

    A., and Srivastava, N

    Batson, J., Spielman, D. A., and Srivastava, N. Twice-ramanujan sparsifiers. SIAM Journal on Computing, 41 0 (6): 0 1704--1721, 2012. doi:10.1137/090772873

    2012 doi

  3. [12]

    Adversarial robustness of streaming algorithms through importance sampling

    Braverman, V., Hassidim, A., Matias, Y., Schain, M., Silwal, S., and Zhou, S. Adversarial robustness of streaming algorithms through importance sampling. In Advances in Neural Information Processing Systems, volume 34, pp.\ 3544--3557, 2021

    2021

  4. [13]

    Quantum M otif C lustering

    Cade, C., Labib, F., and Niesen, I. Quantum M otif C lustering. Quantum , 7: 0 1046, 2023. ISSN 2521-327X. doi:10.22331/q-2023-07-03-1046

    2023 doi

  5. [14]

    H., Louis, A., Tang, Z

    Chan, T.-H. H., Louis, A., Tang, Z. G., and Zhang, C. Spectral properties of hypergraph laplacian and approximation algorithms. Journal of the ACM, 65 0 (3), 2018. doi:10.1145/3178123

    2018 doi

  6. [15]

    and Xu, C

    Chekuri, C. and Xu, C. Minimum cuts and sparsification in hypergraphs. SIAM Journal on Computing, 47 0 (6): 0 2118--2156, 2018. doi:10.1137/18M1163865

    2018 doi

  7. [16]

    P., Peng, R., Gutenberg, M

    Chen, L., Kyng, R., Liu, Y. P., Peng, R., Gutenberg, M. P., and Sachdeva, S. Maximum flow and minimum-cost flow in almost-linear time. In Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, pp.\ 612--623. IEEE, 2022

    2022

  8. [17]

    Near-linear size hypergraph cut sparsifiers

    Chen, Y., Khanna, S., and Nagda, A. Near-linear size hypergraph cut sparsifiers. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pp.\ 61--72, 2020. doi:10.1109/FOCS46700.2020.00015

    2020

  9. [18]

    B., Kyng, R., Miller, G

    Cohen, M. B., Kyng, R., Miller, G. L., Pachocki, J. W., Peng, R., Rao, A. B., and Xu, S. C. Solving SDD linear systems in nearly m ^ 1/2 n time. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp.\ 343--352, 2014

    2014

  10. [19]

    B., Kelner, J., Peebles, J., Peng, R., Sidford, A., and Vladu, A

    Cohen, M. B., Kelner, J., Peebles, J., Peng, R., Sidford, A., and Vladu, A. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In Proceedings of the 2016 IEEE 57th annual symposium on foundations of computer science, pp.\ 583--592. ...

    2016

  11. [20]

    B., Cousins, B., Lee, Y

    Cohen, M. B., Cousins, B., Lee, Y. T., and Yang, X. A near-optimal algorithm for approximating the J ohn ellipsoid. In Beygelzimer, A. and Hsu, D. (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp....

    2019

  12. [21]

    Quantum random access memory

    Giovannetti, V., Lloyd, S., and Maccone, L. Quantum random access memory. Phys. Rev. Lett., 100: 0 160501, Apr 2008. doi:10.1103/PhysRevLett.100.160501

    2008 doi

  13. [22]

    Preparing many copies of a quantum state in the black-box model

    Hamoudi, Y. Preparing many copies of a quantum state in the black-box model. Phys. Rev. A, 105: 0 062440, Jun 2022. doi:10.1103/PhysRevA.105.062440

    2022 doi

  14. [23]

    Hein, M., Setzer, S., Jost, L., and Rangapuram, S. S. The total variation on hypergraphs - learning on hypergraphs revisited. In Burges, C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. (eds.), Advances in Neural Information Processing Systems, volume 26. Curran...

    2013

  15. [25]

    R., Liu, Y

    Jambulapati, A., Lee, J. R., Liu, Y. P., and Sidford, A. Sparsifying generalized linear models. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pp.\ 1665–1675, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400703836. ...

    2024

  16. [26]

    Towards tight bounds for spectral sparsification of hypergraphs

    Kapralov, M., Krauthgamer, R., Tardos, J., and Yoshida, Y. Towards tight bounds for spectral sparsification of hypergraphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp.\ 598–611, 2021. doi:10.1145/3406325.3451061

    2021

  17. [27]

    Spectral hypergraph sparsifiers of nearly linear size

    Kapralov, M., Krauthgamer, R., Tardos, J., and Yoshida, Y. Spectral hypergraph sparsifiers of nearly linear size. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, pp.\ 1159--1170, 2022. doi:10.1109/FOCS52979.2021.00114

    2021

  18. [28]

    Multilevel hypergraph partitioning: applications in vlsi domain

    Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. Multilevel hypergraph partitioning: applications in vlsi domain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7 0 (1): 0 69--79, 1999. doi:10.1109/92.748202

    1999 doi

  19. [29]

    and Wagner, F

    Klimmek, R. and Wagner, F. A simple hypergraph min cut algorithm. Technical Report B, 02, 1996. URL http://edocs.fu-berlin.de/docs/servlets/MCRFileNodeServlet/FUDOCS_derivate_000000000297/1996_02.pdf

    1996

  20. [30]

    and Krauthgamer, R

    Kogan, D. and Krauthgamer, R. Sketching cuts in graphs and hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pp.\ 367–376, 2015. doi:10.1145/2688073.2688093

    2015

  21. [31]

    and Sun, H

    Laenen, S. and Sun, H. Higher-order spectral clustering of directed graphs. Advances in neural information processing systems, 33: 0 941--951, 2020

    2020

  22. [32]

    Lawler, E. L. Cutsets and partitions of hypergraphs. Networks, 3 0 (3): 0 275--285, 1973. doi:https://doi.org/10.1002/net.3230030306

    1973 doi

  23. [33]

    Lee, J. R. Spectral hypergraph sparsification via chaining. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp.\ 207–218, 2023. doi:10.1145/3564246.3585165

    2023

  24. [34]

    Lee, Y. T. and Sidford, A. Path finding methods for linear programming: Solving linear programs in Õ( rank ) iterations and faster algorithms for maximum flow. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp.\ 424--433, 2014. doi:10.1109/FOCS.2014.52

    2014 doi

  25. [35]

    Lee, Y. T. and Sun, H. Constructing linear-sized spectral sparsification in almost-linear time. SIAM Journal on Computing, 47 0 (6): 0 2315--2336, 2018. doi:10.1137/16M1061850

    2018 doi

  26. [36]

    and Milenkovic, O

    Li, P. and Milenkovic, O. Inhomogeneous hypergraph clustering with applications. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, pp.\ 2305–2315, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964

    2017

  27. [37]

    Quadratic decomposable submodular function minimization: Theory and practice

    Li, P., He, N., and Milenkovic, O. Quadratic decomposable submodular function minimization: Theory and practice. Journal of Machine Learning Research, 21 0 (106): 0 1--49, 2020. URL http://jmlr.org/papers/v21/18-790.html

    2020

  28. [38]

    Sublinear quantum algorithms for training linear and kernel-based classifiers

    Li, T., Chakrabarti, S., and Wu, X. Sublinear quantum algorithms for training linear and kernel-based classifiers. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning ...

    2019

  29. [39]

    Quantum speedups for approximating the J ohn ellipsoid, 2024

    Li, X., Song, Z., and Yu, J. Quantum speedups for approximating the J ohn ellipsoid, 2024. URL https://arxiv.org/abs/2408.14018

    2024 arXiv

  30. [40]

    Liu, M., Veldt, N., Song, H., Li, P., and Gleich, D. F. Strongly local hypergraph diffusions for clustering and semi-supervised learning. In Proceedings of the Web Conference 2021, WWW '21, pp.\ 2092–2103, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781...

    2021

  31. [41]

    and Wong, D

    Mak, W.-K. and Wong, D. A fast hypergraph min-cut algorithm for circuit partitioning. Integration, 30 0 (1): 0 1--11, 2000. ISSN 0167-9260. doi:10.1016/S0167-9260(00)00008-0

    doi

  32. [42]

    Nearly Tight Spectral Sparsification of Directed Hypergraphs

    Oko, K., Sakaue, S., and Tanigawa, S.-i. Nearly Tight Spectral Sparsification of Directed Hypergraphs . In 50th International Colloquium on Automata, Languages, and Programming, volume 261, pp.\ 94:1--94:19, 2023. doi:10.4230/LIPIcs.ICALP.2023.94

    2023 doi

  33. [43]

    Partitioning well-clustered graphs: Spectral clustering works! In Conference on learning theory, pp.\ 1423--1455

    Peng, R., Sun, H., and Zanetti, L. Partitioning well-clustered graphs: Spectral clustering works! In Conference on learning theory, pp.\ 1423--1455. PMLR, 2015

    2015

  34. [44]

    Quotient sparsification for submodular functions

    Quanrud, K. Quotient sparsification for submodular functions. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\ 5209--5248, 2024. doi:10.1137/1.9781611977912.187

    2024 doi

  35. [45]

    and Komodakis, N

    Simonovsky, M. and Komodakis, N. Dynamic edge-conditioned filters in convolutional neural networks on graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.\ 3693--3702, 2017

    2017

  36. [46]

    and Yoshida, Y

    Soma, T. and Yoshida, Y. Spectral sparsification of hypergraphs. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\ 2570--2581, 2019. doi:10.1137/1.9781611975482.159

    2019 doi

  37. [47]

    C., and Yoshida, Y

    Soma, T., Tung, K. C., and Yoshida, Y. Online algorithms for spectral hypergraph sparsification. In Vygen, J. and Byrka, J. (eds.), Integer Programming and Combinatorial Optimization, pp.\ 405--417, Cham, 2024. Springer Nature Switzerland. ISBN 978-3-031-59835-7

    2024

  38. [48]

    Revisiting quantum algorithms for linear regressions: Quadratic speedups without data-dependent parameters, 2023

    Song, Z., Yin, J., and Zhang, R. Revisiting quantum algorithms for linear regressions: Quadratic speedups without data-dependent parameters, 2023. URL https://arxiv.org/abs/2311.14823

    2023 arXiv

  39. [49]

    Spielman, D. A. and Srivastava, N. Graph sparsification by effective resistances. SIAM Journal on Computing, 40 0 (6): 0 1913--1926, 2011. doi:10.1137/080734029

    1913 doi

  40. [50]

    Hypergraph clustering based on pagerank

    Takai, Y., Miyauchi, A., Ikeda, M., and Yoshida, Y. Hypergraph clustering based on pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp.\ 1970–1978, 2020. doi:10.1145/3394486.3403248

    1970

  41. [51]

    Hypergcn: A new method for training graph convolutional networks on hypergraphs

    Yadati, N., Nimishakavi, M., Yadav, P., Nitin, V., Louis, A., and Talukdar, P. Hypergcn: A new method for training graph convolutional networks on hypergraphs. In Advances in Neural Information Processing Systems, volume 32, 2019. URL https://proceedings.neurips.cc/paper_files...

    2019

  42. [52]

    Nhp: Neural hypergraph link prediction

    Yadati, N., Nitin, V., Nimishakavi, M., Yadav, P., Louis, A., and Talukdar, P. Nhp: Neural hypergraph link prediction. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, CIKM '20, pp.\ 1705–1714, 2020. doi:10.1145/3340531.3411870

    2020

  43. [53]

    Cheeger inequalities for submodular transformations

    Yoshida, Y. Cheeger inequalities for submodular transformations. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\ 2582–2601, 2019

    2019

  44. [54]

    G., and Chan, T.-H

    Zhang, C., Hu, S., Tang, Z. G., and Chan, T.-H. H. Re-revisiting learning on hypergraphs: Confidence interval, subgradient method, and extension to multiclass. IEEE Transactions on Knowledge and Data Engineering, 32 0 (3): 0 506--518, 2020. doi:10.1109/TKDE.2018.2880448

    2020

  45. [55]

    Learning with hypergraphs: Clustering, classification, and embedding

    Zhou, D., Huang, J., and Sch\" o lkopf, B. Learning with hypergraphs: Clustering, classification, and embedding. In Advances in Neural Information Processing Systems, volume 19, 2006. URL https://proceedings.neurips.cc/paper_files/paper/2006/file/dff8e9c2ac33381546d96deea99229...

    2006

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.