{"id":"d548fa7d-f762-41cd-847e-a1e72c6faf1e","arxiv_id":"2506.11644","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Defines the memory-bounded μ-CONGEST model and establishes a tight Θ(n^{1+o(1)}/μ^{1/2}) round complexity for triangle listing, plus efficient streaming algorithm simulations.","lead":"This paper introduces the μ-CONGEST model, where distributed nodes have both limited message size and limited memory, and proves tight round-memory tradeoffs for triangle listing. It also shows how to run streaming algorithms on a single node by using neighbors' memory to cache edges, and how to parallelize mergeable summaries.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.2 hinges on Lemma A.2, whose proof omits the random-graph construction details and excludes message-storage costs; the memory-round tradeoff is not verified as written.","rationale":"The reader's weakest_assumption correctly identifies the Appendix A expander-routing and decomposition lemmas as load-bearing. My stress-test agrees, and sharpens the concern by pointing to a specific unproven piece inside Lemma A.2: the randomized construction of the sampled virtual-node graph, whose space-round analysis is explicitly omitted. The lemma's own caveat that message storage is excluded is critical because Theorem B.6 routes up to 3μ messages per target node, and the application requires the total memory—routing structures plus message buffers—to stay within O(μ). No calculation in the text shows that this holds for the parameter choices that make α² = n^{o(1)}, which is necessary for the claimed n^{1+o(1)}/√μ round complexity. If the omitted analysis reveals an extra deg(v)·L memory term, then the main upper bound would fail for μ = Θ(Δ). The lower bound (Theorem 1.1) and the streaming simulations (Theorems 1.3–1.8) are less central to this concern, so the conditionality is confined to the triangle-listing tightness claim. A concrete, independent re-derivation of Lemma A.2 would settle the matter without requiring a new model or new experiments.","tokens_in":44392,"tokens_out":49498,"duration_ms":468066,"concrete_test":"Independently re-derive Lemma A.2 without the omitted 'similar to [39]' step, and explicitly track the space used by (i) the sampled random-graph embedding and (ii) the messages buffered at source and destination during the O(α² log n) iterations. For the parameter regime used in Theorem B.6 (L=Θ(μ/x), α=n^{o(1)}, μ≥Δ), verify that total memory per node is O(μ) and rounds are L·α²·2^{O(√log n)}. If the message buffers cost Θ(deg(v)·L) per node, rerun the Theorem 1.2 calculation with that additional term; if the resulting complexity becomes n^{1+o(1)}/√μ · poly(deg(v)/μ), the claimed upper bound is false.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The upper bound for triangle listing (Theorem 1.2) is the crux of the claimed Θ(n^{1+o(1)}/μ^{1/2}) characterization, and it inherits all of its routing power from Lemma A.2 via Theorem B.6. Lemma A.2's proof says 'We omit the details as they are similar to the proofs in [39]' for the construction of the sampled random graph, yet the lemma's entire space-round tradeoff depends on that construction. More concretely, the lemma states μ = ⌈deg(v)/α⌉·2^{O(√log n)} space per node, but immediately adds that this 'does not consider the cost of preparing the messages at the source nodes and the cost of storing the messages at the destination nodes.' In Theorem B.6, every node in S is the target of up to 3μ messages, and in the duplication phase each node in S sends and receives up to 3μ messages; these messages must reside in memory while the routing structure is also stored. The proof does not show a parameter choice α with α² = n^{o(1)} (needed for the n^{1+o(1)}/√μ round bound) for which the routing structure plus the buffered messages fit within O(μ) for all node degrees arising in the cluster decomposition. If the message buffers add an unavoidable Θ(deg(v)·L) term, as the lemma's own caveat suggests, then for μ = Θ(deg(v)) the claimed bound fails. A second, smaller issue appears in Appendix B.3: the line 'then |E_high|≤|E|/4' should read ≥, since the text immediately relies on removing a constant fraction of edges. That typo is cosmetic; the routing lemma issue is load-bearing.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the μ-CONGEST model, a version of CONGEST in which each node has only μ words of memory, and studies the effect of this memory bound on round complexity. It proves a lower bound for k-clique listing (Theorem 1.1), gives a randomized triangle-listing algorithm claimed to run in n^{1+o(1)}/μ^{1/2} rounds for μ ≤ n^{4/3} (Theorem 1.2), and develops several simulations of streaming algorithms, including p-pass algorithms, random-order streams, and one-way, fully mergeable, and composable summaries (Theorems 1.3–1.8). The main advertised contribution is a near-tight memory-round tradeoff for triangle listing.","tokens_in":44738,"tokens_out":23015,"duration_ms":186179,"significance":"If the upper bound is correct, the triangle-listing tradeoff is a genuine contribution: it shows that reducing per-node memory from the Θ(n^{4/3}) used by standard CONGEST algorithms to μ incurs a round cost of roughly n/√μ, up to subpolynomial factors, and the lower-bound window technique is a nice adaptation of the information-theoretic approach of Izumi and Le Gall. The streaming-simulation results are also useful and appear broadly applicable. However, the central upper bound rests on space-efficient expander routing and decomposition lemmas in Appendix A whose proofs are incomplete in important places, and the lower-bound statement contains inaccuracies that need repair. The paper does not provide machine-checked proofs or code, so independent verification of the appendix is the main burden.","major_comments":[{"comment":"Lemma A.2 is load-bearing for Theorem 1.2 through Theorem B.6, but its proof omits the construction details of the sampled random graph (\"We omit the details as they are similar to the proofs in [39]\") and explicitly excludes the cost of storing messages at sources and destinations. In Theorem B.6, each node in S is the target of up to 3μ messages during the first routing and again during the duplication phase; the proof does not show that these messages can be buffered within the O(μ) memory together with the routing structure. Since the lemma's own caveat states that worst-case message storage is deg(v)·L, which is Θ(μ) in this application, the memory accounting must be made explicit, for example by a batching argument, before the n^{1+o(1)}/μ^{1/2} upper bound is established as written.","section":"Appendix A.2.1, Lemma A.2"},{"comment":"The stated round bound μ/x·n^{o(1)} does not follow from Lemma A.2 for all parameters. To fit the routing structure in memory μ for nodes of degree at least x, Lemma A.2 requires α ≳ (x/μ)·2^{O(√log n)} when x > μ, which makes the round term Ω((x/μ)·2^{O(√log n)}), i.e., max(μ/x, x/μ)·n^{o(1)} rather than μ/x·n^{o(1)}. The theorem statement allows arbitrary 1 ≤ x ≤ Δ with no x ≤ μ assumption. The applications in Appendix B happen to fall in the range x ≤ μ, but the tool statement as written is overclaimed and should be revised or qualified.","section":"Appendix B.2, Theorem B.6"},{"comment":"The proof fixes G = G_{n,1/2}, whose maximum degree is Θ(n), so it establishes the lower bound only for ℓ = Θ(n); the theorem's stated dependence on a general ℓ ≤ n is not proven by the given argument. In addition, the entropy of μ words is at most O(μ log n) bits, so the step \"μ = Ω(n^{2(k−1)/k}/L^{2/k})\" should carry a (log n)^{-1} factor. Also, the display Ω(n^{k−1}/(μ^{k/2−1}ℓ)) = Ω(n^{k−2}/μ^{k/2−1}) is not an equality; it should be \"≥\" under ℓ ≤ n, and the final sentence uses n^{k−2} where the derivation yields n^{k−1}. These issues do not destroy the qualitative n^{1+o(1)}/μ^{1/2} tradeoff, but Theorem 1.1 as stated overclaims.","section":"Section 2.1, Theorem 1.1"}],"minor_comments":[{"comment":"In the description of the modified setup, \"w_r = ⌈W/r⌉\" should be \"⌈r/W⌉\"; as written it denotes the wrong window.","section":"Section 2.1"},{"comment":"The notation ρ^{w_max}_{i_max} is confusing: the initial state ρ_i is not window-dependent, so it should be ρ_{i_max}.","section":"Lemma 2.7"},{"comment":"The line \"then |E_high|≤|E|/4\" should read \"≥\"; it follows directly from |E_m| ≥ |E|/2 and |E_low| ≤ |E|/4, and the subsequent argument needs the lower bound to remove a constant fraction of edges.","section":"Appendix B.3"},{"comment":"Minor grammatical issue: \"there exists a algorithm\" should be \"there exists an algorithm\".","section":"Theorem 1.2"},{"comment":"In the proof of Theorem 2.10, \"For Θ(n) ≤ μ ≤ Θ(n^2)\" is inconsistent with the theorem's range μ ≤ n^{2−2/k}; this should be Θ(n^{2−2/k}).","section":"Section 2.2"},{"comment":"References [54] and [55] are duplicate entries for the same Lenzen paper and should be merged.","section":"References"},{"comment":"There is a typo: \"in a streaming fasion\" should be \"in a streaming fashion\".","section":"Definition 3.3"}],"recommendation":"major_revision","confidential_remarks":"The core ideas are plausible and the lower-bound technique is sound in broad strokes, but the journal version must close the gaps in Appendix A/B before I can recommend acceptance. In particular, Lemma A.2 needs a complete proof of the random-graph construction with explicit memory accounting, and Theorem B.6 needs a corrected statement or an additional assumption. The lower-bound statement in Theorem 1.1 should also be restated with the correct log factor and the ℓ parameter handled honestly. I see no grounds for rejection: the issues appear repairable, and the main tradeoff is likely correct."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this is a solid paper worth engaging with. The μ-CONGEST model is new and makes switch memory a first-class parameter, and the triangle listing tradeoff—Ω(n/√μ) lower bound plus an n^{1+o(1)}/√μ algorithm—is a clean, tight result up to subpolynomial factors. The streaming simulation results are more standard (known streaming algorithms married to mergeable summaries), but they're competently done and the applications are reasonable.\n\nThe lower bound is a careful adaptation of Izumi–Le Gall to the memory-bounded setting; the windowing trick to avoid losing the μ/n factor is neat. The upper bound is the real work, and it's in the appendix. The main soft spot is Lemma A.2, the space-efficient expander routing lemma: its proof omits details about the sampled random graph construction and explicitly disclaims message-storage costs. That's a self-containedness gap, not a fatal one—the construction is 'similar to [39]' and a referee can verify it. I checked whether the message buffers break Theorem B.6. Under the paper's global assumption μ≥Δ and with the natural parameter choice α=2^{O(√log n)}, the routing structure costs O(deg(v)) and the up-to-3μ buffered messages are O(μ), so everything fits in O(μ). The proof should have said this explicitly, but the concern doesn't sink the algorithm. There's also a minor typo in Appendix B.3: |E_high|≤|E|/4 should be ≥. That's cosmetic.\n\nThe paper is honest about its limitations—it notes the routing lemma's caveat, and the discussion of μ<Δ suggests future work. Overall the math looks coherent; the main theorem is intricate and deserves independent checking, but I don't see a load-bearing hole. Verdict: send to a serious referee. The audience is researchers in distributed graph algorithms and those working on theory-to-switch bridges. I'd cite it if I were working on memory-constrained distributed computation.","headline":"Solid, citable paper: new μ-CONGEST model, tight triangle-listing tradeoff, and useful streaming simulations; appendix machinery is heavy but the concerns about message buffering don't sink it.","tokens_in":45248,"tokens_out":7371,"would_cite":true,"duration_ms":75591,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","68R10","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper pins down the round complexity of triangle listing under a $\\mu$-word memory limit per node: $\\Theta(n^{1+o(1)}/\\sqrt{\\mu})$ rounds for $\\mu \\le n^{4/3}$, matching a new lower bound up to subpolynomial factors.","keywords":["μ-CONGEST model","distributed graph algorithms","bounded memory","triangle listing","expander decomposition","expander routing","streaming algorithm simulation","mergeable summaries"],"falsifier":"Run the constructions of Lemmas A.2 and A.3 on a small regular expander (a few thousand nodes, degree 3) with $\\alpha$ chosen so that $\\lceil \\deg(v)/\\alpha \\rceil$ is a small constant, and track the peak number of words stored at any node across all routing iterations and decomposition rounds. The lemmas predict a peak of $\\lceil \\deg(v)/\\alpha \\rceil \\cdot 2^{O(\\sqrt{\\log n})}$ words (or $\\lceil \\deg(v)/\\alpha \\rceil \\cdot O(\\log n)$ for the decomposition); if any round requires a node to buffer an amount proportional to $\\deg(v)$, for example holding the previous iteration's routing structure while absorbing the next sampled random graph, the memory bound fails and the $n^{1+o(1)}/\\mu^{1/2}$-round triangle-listing algorithm does not follow, whereas the $\\Omega(n/\\sqrt{\\mu})$ lower bound would still hold.","tokens_in":44217,"feed_emoji":"🔺","tokens_out":22499,"duration_ms":219192,"temperature":0.7,"pith_summary":"The paper introduces $\\mu$-CONGEST, a distributed model in which every node has both the usual per-message bandwidth limit and a hard memory limit of $\\mu$ words, mirroring programmable network switches whose fast on-chip memory is small. It asks how much extra time such a memory cap costs for basic graph tasks, and answers for the central case of triangle listing: no algorithm can list all triangles in fewer than $\\Omega(n/\\sqrt{\\mu})$ rounds, and a matching algorithm runs in $n^{1+o(1)}/\\sqrt{\\mu}$ rounds for every $\\mu \\le n^{4/3}$. The same paper shows that a single node can simulate $p$-pass edge-streaming algorithms in $O(n(\\Delta+p))$ rounds by borrowing its neighbors' memories as a cache, with a matching lower bound $\\Omega(n\\Delta p)$ for sublinear memory, and that mergeable streaming summaries can be aggregated along a spanning tree in time scaling with the summary size rather than the data size. If these bounds are correct, a designer deploying distributed algorithms on memory-poor switches now knows the exact round cost of the memory constraint for a fundamental listing task, and can trade the two resources smoothly.","feed_headline":"Tight memory-speed tradeoff found for triangle listing","feed_subtitle":"Tiny switch memories are no longer a mystery: here is the exact price they extract from triangle listing.","key_machinery":"The argument runs on four load-bearing mechanisms. (1) A windowing reduction for the lower bound: any $\\mu$-memory algorithm can be simulated by one with $3\\mu$ memory that emits cliques only at the ends of non-overlapping windows of $W = \\lceil \\mu/\\ell \\rceil$ rounds, and an entropy argument applied per window shows the busiest node must absorb $\\Omega(n^{2(k-1)/k}/L^{2/k})$ bits of information, forcing $L \\ge \\Omega(n^{k-1}/\\mu^{k/2})$ windows. (2) The round-space tradeoff for expander routing (Lemma A.2): each node simulates its $\\deg(v)$ virtual nodes, a random $1/\\alpha$ fraction is sampled, routing runs on the sampled subgraph, and $\\alpha^2 \\log n$ independent repetitions cover all pairs, giving memory $\\lceil \\deg(v)/\\alpha \\rceil \\cdot 2^{O(\\sqrt{\\log n})}$ at an $\\alpha^2$ factor in rounds. (3) The round-space tradeoff for expander decomposition (Lemma A.3): the parallel instances of the nibble algorithm are assigned random slots among $\\alpha$ rounds so each node stores incoming probabilities of only $\\lceil \\deg(v)/\\alpha \\rceil \\cdot O(\\log n)$ instances, cutting space by $\\alpha$ at an $\\alpha$ factor in rounds. (4) Degree-class synchronization for the listing step: nodes are split into $\\log n$ buckets by degree, the bucket carrying at least $1/\\log n$ of the total bandwidth is selected, and a routing tool (Theorem B.6) delivers edges to each bucket node in synchronized chunks of size $\\mu$ so that the three edges of every triangle arrive in the same memory batch.","core_discovery":"The paper's central claim is that capping each node's memory at $\\mu$ words changes the round complexity of distributed subgraph listing in a precisely measurable way, and that the price can be paid smoothly. In $\\mu$-CONGEST, the standard CONGEST model with an added bound of $\\mu$ words of memory per node and with outputs leaving the node's memory once emitted, every $k$-clique listing algorithm requires $\\Omega(n^{k-2}/\\mu^{k/2-1})$ rounds (Theorem 1.1). For triangles ($k=3$) this bound is tight up to subpolynomial factors: a randomized algorithm lists every triangle in $n^{1+o(1)}/\\mu^{1/2}$ rounds whenever $\\mu \\le n^{4/3}$ (Theorem 1.2), so at linear memory $\\mu = \\Theta(n)$ the complexity is $n^{1/2+o(1)}$. The matching algorithm works by making the two engines of near-optimal triangle enumeration memory-aware: expander routing is executed on a random $1/\\alpha$ fraction of the virtual nodes and repeated $\\alpha^2 \\log n$ times, cutting per-node space by $\\alpha$ at an $\\alpha^2$ factor in rounds (Lemma A.2), while the nibble-based expander decomposition spreads its parallel instances over $\\alpha$ rounds so each node buffers only a $1/\\alpha$ fraction of the incoming probability mass, cutting space by $\\alpha$ at an $\\alpha$ factor in rounds (Lemma A.3). The paper further claims that a single node can simulate $p$-pass edge-streaming algorithms in $O(n(\\Delta+p))$ rounds with $\\mu = M+n$ words by caching all edges in the neighbors of the highest-degree node, that no sublinear-memory simulation can beat $\\Omega(n\\Delta p)$ rounds, that random-order streams can be generated at the same cost via a distributed Fisher-Yates shuffle scheduled by Birkhoff's theorem, and that one-way-mergeable, fully-mergeable, and composable summaries aggregate in $O(\\min\\{nM,\\sqrt{|I|M}\\}+D)$, $O(\\log|I|\\cdot(M\\log(\\Delta M/\\mu)+D))$, and $O(\\log|I|\\cdot(M+D))$ rounds respectively.","pith_inferences":["Looking beyond the paper, the sampling-and-repetition trick behind Lemma A.2 is a generic memory reducer: any distributed routine whose space bottleneck is degree-proportional routing structure should admit the same $\\alpha$-fold space cut at an $\\alpha^2$ round premium, which would extend the tradeoff to spanner and MST constructions built on expander routing.","The windowed entropy argument only needs the $O(m^{k/2})$ bound on clique copies, so the same technique should yield $\\Omega(n/\\sqrt{\\mu})$-type lower bounds for listing other dense subgraphs whenever a counting bound of that shape is available.","A natural testable extension is to check whether the $k$-clique gap for $k>3$ can be closed by a memory-low structure that answers 'which edges were deleted' queries on demand, since the paper handles sub-degree memory only by discarding deleted-edge lists and keeping component identifiers.","Because the distributed shuffle is self-contained, random-order semi-streaming guarantees become available in $\\mu$-CONGEST at the same round cost, which may be the cheapest route to better approximation ratios for matching and spanner problems on this hardware."],"forward_implications":["The memory-round tradeoff for triangle listing is characterized up to subpolynomial factors for all $\\mu \\le n^{4/3}$: an $n^{1+o(1)}/\\sqrt{\\mu}$-round algorithm exists, and no algorithm can be faster.","At linear memory $\\mu = \\Theta(n)$, all triangles are listed in $\\Theta(n^{1/2+o(1)})$ rounds, compared with $\\tilde{O}(n^{1/3})$ rounds when memory is unbounded, so the memory cap costs a factor of roughly $n^{1/6}$ at this point.","Any $p$-pass edge-streaming algorithm using $M$ words can be simulated on one node in $O(n(\\Delta+p))$ rounds with $\\mu = M+n$, and $\\Omega(n\\Delta p)$ rounds are unavoidable when $\\mu \\le n/4$, so the neighbor-caching strategy is worst-case optimal.","Mergeable sketches aggregate in time that depends on the summary size rather than the raw data: approximate quantiles in $O(\\sqrt{m\\epsilon^{-1}\\log(m\\epsilon)}+D)$ rounds, heavy hitters in $O(\\log m\\cdot(\\epsilon^{-1}\\log(\\Delta\\epsilon^{-1}/\\mu)+D))$ rounds, and linear-sketch metrics such as entropy in $O(\\log m\\cdot(M+D))$ rounds.","For $k>3$, the lower bound $\\Omega(n^{k-2}/\\mu^{k/2-1})$ applies to listing $k$-cliques, but the paper achieves the matching listing algorithm only for triangles; the authors state that larger cliques require additional machinery."],"supporting_citations":[{"why":"The near-optimal CONGEST triangle-enumeration framework (expander decomposition, expander routing, recursion on leftover edges) that the $\\mu$-CONGEST upper bound rewrites under per-node memory limits.","marker":"[20]"},{"why":"The information-theoretic CONGEST lower bound for triangle listing whose transcript-entropy argument, extended with the windowing reduction, yields Theorem 1.1.","marker":"[49]"},{"why":"The expander-routing algorithm whose hierarchical virtual-node structure Lemma A.2 samples ($1/\\alpha$ of virtual nodes, $\\alpha^2 \\log n$ repetitions) to reduce memory.","marker":"[39]"},{"why":"The faster expander-routing variant whose round and space figures Lemma A.2 uses to state its concrete bounds.","marker":"[40]"},{"why":"The parallel nibble-based expander decomposition whose $\\deg(v)\\cdot O(\\log n)$ message-buffering cost Lemma A.3 spreads over $\\alpha$ rounds to reduce space.","marker":"[22]"},{"why":"The nibble algorithm (truncated lazy-random-walk probabilities ranked by normalized value) that the decomposition runs in parallel and that Lemma A.3 keeps memory-cheap.","marker":"[70]"},{"why":"Defines the one-way, fully mergeable, and composable summary classes that Theorems 1.6-1.8 simulate and merge.","marker":"[2]"},{"why":"The Fisher-Yates shuffle simulated distributedly in Theorem 1.5 to generate random-order streams for the simulator node.","marker":"[32]"},{"why":"Birkhoff's theorem, used to decompose the $\\Delta \\times \\Delta$ edge-movement matrix into permutation matrices for congestion-free rerouting in Theorem 1.5.","marker":"[9]"}],"fun_headline_variants":["Bounded memory exacts precise round cost in distributed nets","Memory-limited CONGEST: tight tradeoff for clique listing","Triangle listing with small memory: optimal round cost found","Distributed listing with bounded memory: tight complexity","μ-CONGEST: memory bound yields tight speed tradeoffs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the correctness of Lemmas A.2 and A.3 in the appendix: that the existing expander-routing and nibble-based expander-decomposition routines can be re-implemented with per-node memory cut by a factor $\\alpha$ at the price of only an $\\alpha^2$ or $\\alpha$ factor in rounds; if either adaptation fails, the $n^{1+o(1)}/\\mu^{1/2}$-round triangle-listing upper bound does not follow from the text, while the lower bound would survive.","fun_headline_variants_meta":{"raw":{"variants":["Bounded memory exacts precise round cost in distributed nets","Memory-limited CONGEST: tight tradeoff for clique listing","Triangle listing with small memory: optimal round cost found","Distributed listing with bounded memory: tight complexity","μ-CONGEST: memory bound yields tight speed tradeoffs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00023,"raw_usage":{"total_tokens":1676,"prompt_tokens":1335,"completion_tokens":341,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":951,"completion_tokens_details":{"reasoning_tokens":261}},"tokens_in":951,"tokens_out":341,"duration_ms":4810,"temperature":1.0,"reasoning_tokens":261,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:04:29.106505+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the constructions of Lemmas A.2 and A.3 on a small regular expander (a few thousand nodes, degree 3) with $\\alpha$ chosen so that $\\lceil \\deg(v)/\\alpha \\rceil$ is a small constant, and track the peak number of words stored at any node across all routing iterations and decomposition rounds. The lemmas predict a peak of $\\lceil \\deg(v)/\\alpha \\rceil \\cdot 2^{O(\\sqrt{\\log n})}$ words (or $\\lceil \\deg(v)/\\alpha \\rceil \\cdot O(\\log n)$ for the decomposition); if any round requires a node to buffer an amount proportional to $\\deg(v)$, for example holding the previous iteration's routing structure while absorbing the next sampled random graph, the memory bound fails and the $n^{1+o(1)}/\\mu^{1/2}$-round triangle-listing algorithm does not follow, whereas the $\\Omega(n/\\sqrt{\\mu})$ lower bound would still hold.","supporting_citations":[{"cited_title":"Near- optimal distributed triangle enumeration via expander decompositions","cited_arxiv_id":null,"evidence_quote":"The near-optimal CONGEST triangle-enumeration framework (expander decomposition, expander routing, recursion on leftover edges) that the $\\mu$-CONGEST upper bound rewrites under per-node memory limits."},{"cited_title":"Distributed MST and routing in almost mixing time","cited_arxiv_id":null,"evidence_quote":"The expander-routing algorithm whose hierarchical virtual-node structure Lemma A.2 samples ($1/\\alpha$ of virtual nodes, $\\alpha^2 \\log n$ repetitions) to reduce memory."},{"cited_title":"New distributed algorithms in almost mixing time via transformations from parallel algorithms","cited_arxiv_id":null,"evidence_quote":"The faster expander-routing variant whose round and space figures Lemma A.2 uses to state its concrete bounds."},{"cited_title":"with high probability","cited_arxiv_id":null,"evidence_quote":"The nibble algorithm (truncated lazy-random-walk probabilities ranked by normalized value) that the decomposition runs in parallel and that Lemma A.3 keeps memory-cheap."},{"cited_title":"Mergeable summaries","cited_arxiv_id":null,"evidence_quote":"Defines the one-way, fully mergeable, and composable summary classes that Theorems 1.6-1.8 simulate and merge."},{"cited_title":"Fisher and F","cited_arxiv_id":null,"evidence_quote":"The Fisher-Yates shuffle simulated distributedly in Theorem 1.5 to generate random-order streams for the simulator node."},{"cited_title":"Tres observaciones sobre el algebra lineal","cited_arxiv_id":null,"evidence_quote":"Birkhoff's theorem, used to decompose the $\\Delta \\times \\Delta$ edge-movement matrix into permutation matrices for congestion-free rerouting in Theorem 1.5."}],"review_version":1}