Pith. sign in

REVIEW 4 major objections 6 minor 44 references

Distributed Triangle and Simplex Enumeration in Hypergraphs

T0 review · 4 major / 6 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read The paper proves optimal round bounds—O(n^{r−5/3}/log n)—for distributed triangle enumeration in r-uniform hypergraphs, and gives nearly tight bounds for sparse and everywhere-sparse hypergraphs.

desk verdict A useful but unfinished framework for distributed hypergraph triangle enumeration; the main lower bound rests on an imported lemma that is not proved for hypergraphs and the manuscript has multiple broken artifacts. read the letter →

arxiv 2602.17834 v2 pith:37LT7GVG submitted 2026-02-19 cs.DC

Duncan Adamson , Will Rosenbaum , Paul G. Spirakis This is my paper · ORCID
classification cs.DC MSC 05C6568W15
keywords hypergraphsdistributedalgorithmstriangleenumerationCLIQUEmodelPRIMALCONGESTroundcomplexityextremalhypergraphtheorysparse
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 asks: when a network's communication structure is a hypergraph—where an edge can connect arbitrarily many vertices at once—how many rounds are needed for every triangle in the hypergraph to be output somewhere? It introduces six distributed models that generalize the CONGEST model, then pins down the round complexity of triangle enumeration in the strongest of them. The main result is that in the CLIQUE and PRIMAL CONGEST models, r-uniform hypergraphs can be solved in O(n^{r−5/3}/log n) rounds and no algorithm can do better. The load-bearing step is a new extremal bound on how many triangles a fixed number of hyperedges can support. For sparse and 'everywhere sparse' hypergraphs, the paper gives O(n)-round and O(μ r + log n)-round algorithms, with near-matching lower bounds.

What carries the argument

The load-bearing tool is an extremal bound (Theorem 3.8): an r-uniform hypergraph with m hyperedges can contain at most (√2/3)(m·C(n−3, r−2)·C(r,2))^{3/2} triangles. The proof passes through an induced multigraph—replace each hyperedge by a clique on its vertices, with multiplicity bounded by C(n−2, r−2)—and then applies matrix-trace inequalities to relate triangle count to edge count. This bound drives the lower bound, forcing any vertex that outputs many triangles to have witnessed many hyperedges. The upper bound uses a partition of all possible vertex triples among the n vertices, so that each vertex only needs to learn the characteristic vectors of O(n^{r−2/3}) hyperedges, routed with a

What would settle it

Compute the mutual information I(E; T_v) for a small 3-uniform hypergraph—for instance, the example in the paper with three edges sharing vertices—and check whether Lemma 3.20's inequality holds: if a vertex's output triangles contain more edges in expectation than the mutual information between the input edge indicators and the output set can account for, the lower bound fails. Separately, in the sparse-hypergraph reduction of Theorem 4.4, count the messages that a single EDGE CLIQUE round can send along parallel edges (up to Δ2 per pair) and check whether the claimed 2-round CLIQUE simulatio

Watch

Extended reading notes

Core claim

The central claim is that distributed triangle enumeration in r-uniform hypergraphs has a tight, optimal round complexity in the two most natural models: the CLIQUE model (every pair of vertices can exchange short messages each round) and PRIMAL CONGEST (vertices can exchange messages with any other vertex sharing a hyperedge). The algorithm partitions the n^3 possible vertex triples among the n vertices and routes each vertex the characteristic vectors of incident hyperedges it needs; using a deterministic routing scheme, this runs in O(n^{r−5/3}/log n) rounds. The matching lower bound uses a random r-uniform hypergraph where each hyperedge is present with probability 1/2, shows some vertex

Load-bearing premise

The entire lower bound rests on Lemma 3.20 (Section 3.2), an information-theoretic inequality imported without proof from the graph setting: the set of triangles output by a vertex must carry mutual information at least the expected number of edges contained in those triangles; if that inequality fails for hypergraphs, the Ω(n^{r−5/3}/log n) bound collapses.

Editorial extensions

If this is right

  • If the bounds are correct, no distributed algorithm can enumerate triangles in r-uniform hypergraphs faster than Ω(n^{r−5/3}/log n) rounds in CLIQUE or PRIMAL CONGEST; the O(n^{r−5/3}/log n) algorithm is therefore optimal.
  • The lower bound transfers to the EDGE CLIQUE model and the weaker EDGE BROADCAST, EDGE UNICAST, EDGE SOLOCAST, and EDGE PAIRCAST models, giving Ω(n^{1/3}/log n) rounds there, and the model-simulation results make the relative power of the six models precise up to O(r^2) factors.
  • For sparse hypergraphs, triangle enumeration is solvable in O(n) rounds in EDGE BROADCAST and PRIMAL CONGEST, and any faster PRIMAL CONGEST algorithm is impossible: Ω(n^{1−ε}) rounds are required for every ε > 0.
  • For hypergraphs with maximum density μ, triangle enumeration runs in O(μ r + log n) rounds without knowing μ in advance, and Ω(μ^{1−ε}) rounds are needed in PRIMAL CONGEST, so the μ-dependence is essentially tight.
  • The paper's model hierarchy, maximum-density parameter, layered peeling procedure, and graph-reduction techniques provide a template for generalizing other CONGEST algorithms to hypergraphs.

Reading between the lines

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

  • If the imported inequality Lemma 3.20 holds, the same information-theoretic framework likely extends to other subgraph enumeration tasks (e.g., clique or simplex listing) in hypergraphs, with extremal edge-support bounds playing the same role.
  • The EC-model conjecture (an eO(n^{1/3}) round algorithm for bounded-rank hypergraphs) is explicitly left open; the paper's own remarks suggest a suitable generalization of expander-decomposition routing that exploits parallel edges is the natural route.
  • The sparse lower-bound reduction in Theorem 4.4 appears to omit the up-to-Δ2 parallel-edge messages that a single EDGE CLIQUE round can carry; if that gap is real, the Ω(n^{1−ε}) PRIMAL CONGEST bound for sparse hypergraphs may need a different construction, or may only hold under an additional assumption.
  • The maximum-density parameter μ and the layered peeling decomposition are natural hypergraph analogues of arboricity; they could become standard parameters for other distributed hypergraph problems such as coloring or independent-set computation.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

Summary. The paper initiates the study of distributed triangle enumeration in hypergraphs under several new communication models (PC, EC, EB, EU, ES, EP). Its main claims are: (i) an O(n^{r-5/3}/\log n)-round CLIQUE-model algorithm for triangle enumeration in r-uniform hypergraphs (Theorem 3.1); (ii) a matching Ω(n^{r-5/3}/\log n) lower bound in CLIQUE and PC (Theorem 3.3), based on a new extremal bound on the number of hyperedges needed to support many triangles (Theorem 3.8); (iii) algorithms for sparse and everywhere-sparse hypergraphs with nearly matching lower bounds (Theorems 4.2, 4.4, 4.14, 4.15); and (iv) a lattice of simulation results among the new models (Propositions 2.2 and 2.3). The upper-bound algorithm is a direct generalization of Dolev–Lenzen–Peled, and the lower-bound strategy follows Izumi–Le Gall. The paper does not actually contain algorithms or theorems for simplex enumeration despite the title and abstract.

Significance. If the main theorems are correct, the paper makes a substantial contribution: it generalizes the optimal triangle-enumeration bounds for CONGEST/CLIQUE from graphs to hypergraphs, introduces a useful family of hypergraph communication models, and provides a novel extremal bound (Theorem 3.8) that may be of independent interest. The sparse-hypergraph results and the maximum-density structural lemma are also valuable and are likely to be reused. The paper is not merely an incremental adaptation: the rank-dependent exponent n^{r-5/3} is a genuine new phenomenon. However, the lower-bound argument is not self-contained, and one of the sparse lower-bound proofs is written in a way that does not support the stated model. These issues must be resolved before the central optimality claims can be accepted.

major comments (4)
  1. [§3.2, Lemma 3.20 and proof of Theorem 3.3] Lemma 3.20 is load-bearing but is imported from [22] with only the statement that the proof is identical and is not reproduced. This is not acceptable for the central lower bound: the graph proof may not transfer verbatim because in a hypergraph a single hyperedge can participate in many output triangles assigned to different vertices or to the same vertex. The paper must either supply the full proof adapted to hypergraphs or give a precise reference to a statement that covers this setting. Moreover, the lemma is stated for an arbitrary fixed vertex v, but the proof applies it to w = argmax_v |T_v|, a data-dependent vertex. No averaging or symmetrization is provided. As written, the application is unjustified; it can likely be repaired by summing over fixed vertices and using I(E;T) ≥ max_v I(E;T_v), but this needs to be written out.
  2. [§3.2, proof of Theorem 3.3] The sentence "Applying Lemma 3.20, we find that I(E;T_w)=Ω(n^{3r-4}) as well" is not a consequence of the cited lemma. Lemma 3.20 gives I(E;T_w) ≥ E[|E(T_w)|], and Corollary 3.9 only implies E[|E(T_w)|] = Ω(n^{r-2/3}/r^2) when |T_w| = Ω(n^{3r-4}). The quantity |E(T_w)| can be much smaller than |T_w|. The later line also writes "H(ρ_w)=Ω(n^{r-2/3}/r^2)" where H(π_w) is clearly intended. These seem to be typographical slips rather than fatal errors, but the entropy chain must be rewritten coherently.
  3. [§4.2, proof of Theorem 4.4] The reduction as written simulates EC rounds with CLIQUE on the subhypergraph H' and concludes a lower bound for EC, not for the stated PC model. In particular, the claim that "a single round of EC in H' can be simulated by a single round of CLIQUE on H'" is false: EC permits a pair of vertices to exchange up to deg(u,v) messages per round, and in the constructed dense subhypergraph this can be as large as O(n^{r-2}), whereas CLIQUE permits only one message per pair per round. If the intended reduction was from PC (which is plausible, since PC on H can be simulated by CLIQUE on H' in two rounds), then the text uses "EC" where "PC" is meant. As written, the proof does not establish Theorem 4.4.
  4. [Title and abstract] The title and abstract promise "simplex enumeration", but the paper contains no simplex enumeration algorithm or theorem; Section 5.1 explicitly lists simplices as future work. The claims in the abstract should be corrected to match the actual contributions (triangle enumeration only), or the missing simplex results must be supplied.
minor comments (6)
  1. [Algorithm 1, line 3] The partition is described as "partition of [n] into n^{2/3} parts of size n^{1/3}", but the surrounding text and the proof require n^{1/3} parts of size n^{2/3}. This should be corrected.
  2. [§3.1, proof of Theorem 3.1] The proof cuts off mid-sentence: "Note that each such triangle is" — the correctness argument is incomplete and must be finished.
  3. [Algorithm 2] The code contains the literal placeholder "[TODO: describe the second procedure]". This must be removed and the missing pseudo-code supplied.
  4. [§3.2] The references to "Lemma 4.3 in [CITE]" and "Lemma 4.2 in [CITE]" are unresolved placeholders. They should be replaced with the actual lemma numbers from [22] or restated.
  5. [§3.2, Eq. (24) and following lines] Equation (24) has a notation typo: "E[E(|T_v|)]" should presumably be "E[|E(T_v)|]". Also, in the final paragraph of the proof of Theorem 3.3, "H(ρ_w)=Ω(n^{r-2/3}/r^2)" should read "H(π_w)=...".
  6. [§3.3, proof of Theorem 3.21] The message-size analysis says O(min{r Δ, n^{r-2}/log n + 1}) but the theorem statement uses Δ2; presumably the first term should be O(r Δ2). Please align the notation.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reductions found; central claims rest on novel combinatorial bounds and external machinery, not on self-referential inputs.

full rationale

The derivation chain is not circular. The CLIQUE upper bound (Theorem 3.1) is built by directly routing characteristic vectors with Lenzen's routing scheme, using the same triple partition as Dolev–Lenzen–Peled; no fitted parameter is renamed as a prediction. The lower bound (Theorem 3.3) is supported by a new extremal bound (Theorem 3.8), proved from Rivin's trace inequality through the induced multigraph G{H}, and by Lemma 3.20 imported from Izumi–Le Gall [22], an external published result. The paper explicitly declines to reproduce that proof ('The proof in our setting is identical to that of Izumi and Le Gall, so we do not reproduce the argument here'), which raises a proof-transfer risk for hypergraphs, but relying on an external lemma is not a circular step: the lemma is not an input of the target theorem and is not derived from the paper's own claims. The authors' own prior work [2] appears only in a related-work list and is not load-bearing; no uniqueness theorem or ansatz is smuggled in via self-citation. The sparse-hypergraph lower bounds reuse the paper's own Theorem 3.3 by reduction, which is legitimate reuse rather than circularity. Two non-circular correctness concerns are worth flagging: Lemma 3.20 is asserted without a hypergraph proof, and Theorem 4.4's statement that 'a single round of EC in H' can be simulated by a single round of CLIQUE on H'' appears to ignore the O(Δ2) parallel-edge bandwidth EC provides. These are proof gaps, not cases where a claimed prediction reduces by construction to its inputs.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No numerical constants are fitted: the results are asymptotic and parameter-free, with r, Δ, and μ treated as inputs. The paper relies on standard external theorems for routing, mixing, and information theory. The new communication models and the density parameter are definitions, not extra entities postulated to explain a result.

assumptions (6)
  • domain assumption KT1 initial knowledge: each vertex knows its 1-neighborhood, port numbering, and incident-edge structure; messages have B=Θ(log n) bits.
    Section 2.2 assumes KT1 for the whole paper. If vertices knew KT2, triangle listing becomes trivial, so all bounds depend on this modeling choice.
  • standard math Lemma 3.20 (Izumi–Le Gall information-theoretic inequality): I(E;T_v) ≥ E[|E(T_v)|] for hypergraph triangle enumeration.
    Imported from [22] without proof and used to derive the CLIQUE/PC lower bound. The paper states the proof is identical to the graph case but does not reproduce it; a missing [CITE] makes it unverifiable in the text.
  • standard math Rivin's Corollary 1: (tr(A^k))² ≤ (tr(A²))^k for symmetric matrices.
    Used in Corollary 3.17 and Theorem 3.8 to bound the number of triangles in a multigraph of bounded multiplicity.
  • standard math Lenzen's deterministic congested-clique routing scheme.
    Used in Theorem 3.1 to route O(n^{4/3}) messages of length O(n^{r−2}) per vertex in optimal rounds.
  • standard math Chang et al.'s expander-decomposition and expander-routing machinery for CONGEST triangle enumeration.
    Used in Theorem 3.21 to obtain eO(n^{r−5/3})-round bounds in EC and PC.
  • standard math Nash-Williams arboricity characterization and the Barenboim–Elkin layered-decomposition technique.
    Motivates Definition 4.8 of maximum density and Proposition 4.9, which underpin the everywhere-sparse algorithms.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distributed Triangle and Simplex Enumeration in Hypergraphs." pith.science (2026). https://pith.science/paper/37LT7GVG

@misc{pith2026260217834,
  author       = {Pith},
  title        = {Pith review of: Distributed Triangle and Simplex Enumeration in Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/37LT7GVG}},
  note         = {Machine review of arXiv:2602.17834}
}
read the original abstract

In the last decade, subgraph detection and enumeration have emerged as central problems in distributed graph algorithms. This is largely due to the problems' theoretical challenges and practical applications. In this paper, we initiate the systematic study of distributed sub-hypergraph enumeration in hypergraphs. To this end, we (1) introduce several computational models for hypergraphs that generalize the CONGEST model for graphs and evaluate their relative computational power, (2) devise algorithms for distributed triangle and simplex enumeration in our computational models and prove their optimality in two such models by showing matching lower bounds, (3) introduce classes of sparse and "everywhere sparse" hypergraphs and describe efficient distributed algorithms for triangle and simplex enumeration in these classes, and (4) describe general techniques that we believe to be useful for designing efficient algorithms in our hypergraph models.

Figures

Figures reproduced from arXiv: 2602.17834 by the authors.

Figure 1
Figure 1. A figure demonstrating the relationships between models given in Proposition 2.2. Di [PITH_FULL_IMAGE:figures/full_fig_p013_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

44 extracted references · 1 linked inside Pith

  1. [22]

    Triangle Finding and Listing in CONGEST Networks

    Taisuke Izumi and Fran¸ cois Le Gall. “Triangle Finding and Listing in CONGEST Networks”. In:Proceedings of the ACM Symposium on Principles of Distributed Computing. Washington DC USA: ACM, July 2017, pp. 381–389

    2017

  2. [1]

    Distributed coloring of hypergraphs

    Duncan Adamson, Magn´ us M Halld´ orsson, and Alexandre Nolin. “Distributed coloring of hypergraphs”. In:International Colloquium on Structural Information and Communication Complexity. Springer. 2023, pp. 89–111

    2023

  3. [2]

    Distributed weak independent sets in hypergraphs: Upper and lower bounds

    Duncan Adamson, Will Rosenbaum, and Paul G Spirakis. “Distributed weak independent sets in hypergraphs: Upper and lower bounds”. In:International Symposium on Algorithmics of Wireless Networks. Springer. 2025, pp. 1–16

    2025

  4. [3]

    A Survey on Hypergraph Representation Learning

    Alessia Antelmi et al. “A Survey on Hypergraph Representation Learning”. In:ACM Com- puting Surveys56.1 (Jan. 2024), pp. 1–38

    2024

  5. [4]

    The Internet of Things: A Survey

    Luigi Atzori, Antonio Iera, and Giacomo Morabito. “The Internet of Things: A Survey”. In: Computer Networks54.15 (Oct. 2010), pp. 2787–2805

    2010

  6. [5]

    A Trade-off between Information and Communication in Broadcast Protocols

    Baruch Awerbuch, Oded Goldreich, Ronen Vainish, and David Peleg. “A Trade-off between Information and Communication in Broadcast Protocols”. In:Journal of The Acm37.2 (Apr. 1990), pp. 238–256

    1990

  7. [6]

    Distributed Maximal Matching and Maximal Independent Set on Hypergraphs

    Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. “Distributed Maximal Matching and Maximal Independent Set on Hypergraphs”. In:Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2632–2676

    2023

  8. [7]

    Distributed Graph Coloring: Fundamentals and Re- cent Developments

    Leonid Barenboim and Michael Elkin. “Distributed Graph Coloring: Fundamentals and Re- cent Developments”. In:Synthesis Lectures on Distributed Computing Theory4.1 (July 2013), pp. 1–171. 34

    2013

Show all 44 references
  1. [8]

    Sublogarithmic Distributed MIS Algorithm for Sparse Graphs Using Nash-Williams Decomposition

    Leonid Barenboim and Michael Elkin. “Sublogarithmic Distributed MIS Algorithm for Sparse Graphs Using Nash-Williams Decomposition”. In:Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing. Toronto Canada: ACM, Aug. 2008, pp. 25–34

    2008

  2. [9]

    Networks beyond Pairwise Interactions: Structure and Dynamics

    Federico Battiston et al. “Networks beyond Pairwise Interactions: Structure and Dynamics”. In:Physics Reports874 (2020), pp. 1–92

    2020

  3. [10]

    Higher-Order Organization of Com- plex Networks

    Austin R. Benson, David F. Gleich, and Jure Leskovec. “Higher-Order Organization of Com- plex Networks”. In:Science353.6295 (July 2016), pp. 163–166

    2016

  4. [11]

    Simplicial Closure and Higher-Order Link Prediction

    Austin R. Benson et al. “Simplicial Closure and Higher-Order Link Prediction”. In:Proceed- ings of the National Academy of Sciences115.48 (Nov. 2018)

    2018

  5. [12]

    Network Traffic Characteristics of Data Centers in the Wild

    Theophilus Benson, Aditya Akella, and David A. Maltz. “Network Traffic Characteristics of Data Centers in the Wild”. In:Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement. Melbourne Australia: ACM, Nov. 2010, pp. 267–280

    2010

  6. [13]

    Mathematical Engineering

    Alain Bretto.Hypergraph Theory: An Introduction. Mathematical Engineering. Heidelberg: Springer International Publishing, 2013

    2013

  7. [14]

    Keren Censor-Hillel.Distributed Subgraph Finding: Progress and Challenges. 2025

    2025

  8. [15]

    Counting Simplices in Hypergraph Streams

    Amit Chakrabarti and Themistoklis Haris. “Counting Simplices in Hypergraph Streams”. In: LIPIcs, Volume 244, ESA 2022244 (2022). Ed. by Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, 32:1–32:19

    2022

  9. [16]

    Near-Optimal Dis- tributed Triangle Enumeration via Expander Decompositions

    Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang. “Near-Optimal Dis- tributed Triangle Enumeration via Expander Decompositions”. In:Journal of the ACM68.3 (June 2021), pp. 1–36

    2021

  10. [17]

    “Tri, Tri Again

    Danny Dolev, Christoph Lenzen, and Shir Peled. ““Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting”. In:Distributed Computing. Ed. by David Hutchi- son et al. Vol. 7611. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 195–209

    2012

  11. [18]

    Distributed MST and Routing in Al- most Mixing Time

    Mohsen Ghaffari, Fabian Kuhn, and Hsin-Hao Su. “Distributed MST and Routing in Al- most Mixing Time”. In:Proceedings of the ACM Symposium on Principles of Distributed Computing. Washington DC USA: ACM, July 2017, pp. 131–140

    2017

  12. [19]

    New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms

    Mohsen Ghaffari and Jason Li. “New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms”. In:LIPIcs, Volume 121, DISC 2018121 (2018), 31:1–31:16

    2018

  13. [20]

    The Strength of Weak Ties

    Mark S. Granovetter. “The Strength of Weak Ties”. In:American Journal of Sociology78.6 (1973), pp. 1360–1380

    1973

  14. [21]

    Scalable Hypergraph Learning and Processing

    Jin Huang, Rui Zhang, and Jeffrey Xu Yu. “Scalable Hypergraph Learning and Processing”. In:2015 IEEE International Conference on Data Mining. Atlantic City, NJ, USA: IEEE, Nov. 2015, pp. 775–780

    2015

  15. [23]

    A Space-Efficient Streaming Algorithm for Esti- mating Transitivity and Triangle Counts Using the Birthday Paradox

    Madhav Jha, C. Seshadhri, and Ali Pinar. “A Space-Efficient Streaming Algorithm for Esti- mating Transitivity and Triangle Counts Using the Birthday Paradox”. In:ACM Transactions on Knowledge Discovery from Data9.3 (Apr. 2015), pp. 1–21. 35

    2015

  16. [24]

    A Model of Computation for MapReduce

    Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. “A Model of Computation for MapReduce”. In:Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Dis- crete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010. 2010, pp. 938– 948

    2010

  17. [25]

    Multilayer Networks

    M. Kivela et al. “Multilayer Networks”. In:Journal of Complex Networks2.3 (Sept. 2014), pp. 203–271

    2014

  18. [26]

    LOTUS: Locality Op- timizing Triangle Counting

    Mohsen Koohi Esfahani, Peter Kilpatrick, and Hans Vandierendonck. “LOTUS: Locality Op- timizing Triangle Counting”. In:Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Seoul Republic of Korea: ACM, Apr. 2022, pp. 219–233

    2022

  19. [27]

    Efficient distributed computation of MIS and generalized MIS in linear hypergraphs

    Fabian Kuhn and Chaodong Zheng. “Efficient distributed computation of MIS and generalized MIS in linear hypergraphs”. In:arXiv preprint arXiv:1805.03357(2018)

    2018 arXiv

  20. [28]

    Distributed Symmetry Breaking in Hypergraphs

    Shay Kutten, Danupon Nanongkai, Gopal Pandurangan, and Peter Robinson. “Distributed Symmetry Breaking in Hypergraphs”. In:Distributed Computing. Ed. by Fabian Kuhn. Vol. 8784. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, pp. 469–483

    2014

  21. [29]

    Encapsulation Structure and Dynamics in Hyper- graphs

    Timothy LaRock and Renaud Lambiotte. “Encapsulation Structure and Dynamics in Hyper- graphs”. In:Journal of Physics: Complexity4.4 (Dec. 2023), p. 045007

    2023

  22. [30]

    Geon Lee, Fanchen Bu, Tina Eliassi-Rad, and Kijung Shin.A Survey on Hypergraph Mining: Patterns, Tools, and Generators. Feb. 2025

    2025

  23. [31]

    Optimal Deterministic Routing and Sorting on the Congested Clique

    Christoph Lenzen. “Optimal Deterministic Routing and Sorting on the Congested Clique”. In:ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22-24, 2013. 2013, pp. 42–50

    2013

  24. [32]

    Locality in Distributed Graph Algorithms

    N. Linial. “Locality in Distributed Graph Algorithms”. In:SIAM Journal on Computing21.1 (Feb. 1992), pp. 193–201

    1992

  25. [33]

    Minimum-Weight Spanning Tree Construction in O(Log Log n) Communication Rounds

    Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. “Minimum-Weight Spanning Tree Construction in O(Log Log n) Communication Rounds”. In:SIAM Journal on Comput- ing35.1 (Jan. 2005), pp. 120–131

    2005

  26. [34]

    Network Motifs: Simple Building Blocks of Complex Networks

    R. Milo et al. “Network Motifs: Simple Building Blocks of Complex Networks”. In:Science 298.5594 (2002), pp. 824–827

    2002

  27. [35]

    Decomposition of Finite Graphs into Forests

    C. St.J. A. Nash-Williams. “Decomposition of Finite Graphs into Forests”. In:Journal of the London Mathematical Societys1-39.1 (1964), pp. 12–12

    1964

  28. [36]

    The Structure and Function of Complex Networks

    M. E. J. Newman. “The Structure and Function of Complex Networks”. In:SIAM Review 45.2 (Jan. 2003), pp. 167–256

    2003

  29. [37]

    On the Distributed Complex- ity of Large-Scale Graph Computations

    Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. “On the Distributed Complex- ity of Large-Scale Graph Computations”. In:ACM Transactions on Parallel Computing8.2 (June 2021), pp. 1–28

    2021

  30. [38]

    Society for Industrial and Applied Mathematics, 2000

    David Peleg.Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000

    2000

  31. [39]

    Peterson and Bruce S

    Larry L. Peterson and Bruce S. Davie.Computer Networks, Fifth Edition: A Systems Ap- proach. 5th ed. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2011

    2011

  32. [40]

    Counting Cycles and Finite Dimensional Lp Norms

    Igor Rivin. “Counting Cycles and Finite Dimensional Lp Norms”. In:Advances in Applied Mathematics29.4 (Nov. 2002), pp. 647–662. 36

    2002

  33. [41]

    Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains

    Alistair Sinclair and Mark Jerrum. “Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains”. In:Information and Computation82.1 (July 1989), pp. 93–133

    1989

  34. [42]

    Triangle-Aware Spectral Spar- sifiers and Community Detection

    Konstantinos Sotiropoulos and Charalampos E. Tsourakakis. “Triangle-Aware Spectral Spar- sifiers and Community Detection”. In:Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. Virtual Event Singapore: ACM, Aug. 2021, pp. 1501– 1509

    2021

  35. [43]

    Counting Triangles in Real-World Networks Using Projec- tions

    Charalampos E. Tsourakakis. “Counting Triangles in Real-World Networks Using Projec- tions”. In:Knowledge and Information Systems26.3 (Mar. 2011), pp. 501–520

    2011

  36. [44]

    Collective Dynamics of ‘Small-World’ Networks

    Duncan J Watts and Steven H Strogatz. “Collective Dynamics of ‘Small-World’ Networks”. In:Nature393.6684 (June 1998). 37

    1998

Pith tools

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