{"id":"37c1db26-7484-4f79-86ff-99db7cb2d7a5","arxiv_id":"2607.09170","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.5,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"MIS and MM on hyperbolic random graphs admit Õ(log^{5/3} log n)-round LOCAL algorithms and an Ω(log log n / log log log n) lower bound, via new d-ary tree substructures.","lead":"Distributed algorithms for maximal independent set and maximal matching run exponentially faster on hyperbolic random graphs than on worst-case graphs, yet still require super-constant rounds. The work proves matching poly-loglog upper and lower bounds and shows that geometric coordinates further accelerate matching.","discovery_kind":"new_application","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the HRG-to-tree coupling (Lemma 24) as the technically most sensitive step. That coupling, however, is carefully engineered: the height reduction h = ⌊ h_hrg/100⌋ and the radius restriction r < h_hrg/200 guarantee that neither the leaves nor the attachment vertex are visible inside any r-hop view. The geometric construction supplies exactly the required induced d-ary trees a.a.s., and the round-elimination sequences of Balliu et al. remain valid under the doubled error probability. Consequently the asymptotic lower bound stands, the matching upper bounds are obtained by a clean constant-round geometric shattering, and the overall verdict ACCEPT with high confidence is justified. No adjustment is needed.","tokens_in":62007,"tokens_out":526,"duration_ms":6422,"concrete_test":"Independently re-derive the non-edge claim of Lemma 20 (Case 2) for the lowest-common-ancestor configuration using only the hyperbolic distance formula (1) and the box angular widths of Definition 19; if the inequality δ_φ(u,v) > \theta_R(r(u),r(v)) fails for any admissible m = ω(1), the tree-embedding argument collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The lower-bound transfer (Lemma 24) and the geometric tree construction (Theorem 18 / Corollary 23) are the most delicate steps, but both appear internally consistent. The radial placement of the d-ary trees (root at layer ℓ_{0} ≈ log log n, children offset by 2 log m) together with the buffer sectors Ψ and the a.a.s. emptiness of the central disk B_{0}(r*) ensure that an r-round view with r < h_hrg/200 never reaches the unique cut-edge. The induced error probability 2p is absorbed by the general round-elimination statement (Theorem 44 / Appendix C) without changing the asymptotic Ω(log log n / log log log n). The upper-bound shattering (Propositions 14 and 17) likewise rests on standard Chernoff + Poisson arguments that hold for the stated parameter ranges. No hidden assumption that would invalidate the asymptotic claims of Theorems 1–2 was found.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies distributed MIS and maximal matching on threshold hyperbolic random graphs. It proves that both problems require Ω(log log n / log log log n) rounds a.a.s. on the giant component in the LOCAL model (Theorem 2), by constructing polynomially many induced d-ary trees of height θ(log_d log n) attached by a single cut-edge (Theorem 18 / Corollary 23) and transferring known tree lower bounds via a careful coupling (Lemma 24). Matching upper bounds of Õ(log^{5/3} log n) LOCAL and Õ(log^{3} log n) CONGEST are obtained by a constant-round geometric shattering procedure that realises angular separators (Theorem 1, Propositions 14 and 17). When nodes know their hyperbolic coordinates, MM improves further to O(log log log n) CONGEST rounds (Theorem 3).","tokens_in":62266,"tokens_out":827,"duration_ms":9454,"significance":"The work cleanly separates the complexity of MIS/MM from that of Δ+1-colouring on the same generative model, showing that the dramatic constant-round colouring result of Maus–Ruff does not extend to all classical symmetry-breaking problems. The geometric tree-embedding theorem is of independent structural interest and supplies a reusable lower-bound transfer technique for other locally checkable problems on HRGs. The shattering analysis is self-contained and does not rely on the flawed off-the-shelf shattering arguments recently identified in the literature. The embedding-aware separation for MM is a clean illustration that geometric side information can beat pure combinatorial lower bounds. Full proofs, concentration arguments, and an explicit generalisation of round-elimination to arbitrary error probability (Appendix C) are supplied.","major_comments":[],"minor_comments":[{"comment":"In the abstract and Theorem 1 the CONGEST bound is written Õ(log^{3} log n); the footnote and the MM analysis claim the slightly stronger O(log^{3} log n). Align the statements.","section":"Abstract / Theorem 1"},{"comment":"The constant 40 appearing in the tiling (Eq. (26) and Lemma 27) is chosen for convenience; a short remark that any sufficiently large constant works would help readers who wish to re-use the tiling.","section":"Section 7, Tiling"},{"comment":"Figure 1 caption refers to “Theorem 3 (MM)” and “Theorem 3 (MIS)”; the figure itself would be clearer if the two embedding-aware bounds were drawn with distinct markers.","section":"Figure 1"},{"comment":"Lemma 9 is used repeatedly; a one-sentence geometric intuition (shared neighbour of larger radius forces a triangle) would make later applications easier to follow.","section":"Section 4, Lemma 9"},{"comment":"In Appendix A the parameter ε = (1-1/(2α))/(2t(t+2)) is tuned so that the residual degree stays polynomial after any constant number of Luby rounds; a brief numerical example for a concrete α would make the calculation more transparent.","section":"Appendix A"}],"recommendation":"accept","confidential_remarks":"The manuscript is already in excellent shape for a top theory venue. The only potential editorial concern is that the lower-bound transfer (Lemma 24) is somewhat delicate; a careful copy-editor pass on the radial-placement constants would be worthwhile, but I see no reason to delay acceptance."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles the natural follow-up to the SODA’26 2-round colouring result on hyperbolic random graphs. The headline is clean: MIS and maximal matching sit at Θ̃(polyloglog n) on HRGs, with a matching lower bound of Ω(log log n / log log log n) that comes from an explicit construction of polynomially many induced d-ary trees of height roughly log_d log n attached by a single cut-edge to the giant component.\n\nWhat is new is the geometric shattering (two carefully tuned Luby steps that carve angular separators of width polylog n / n) and the tree-embedding argument itself (nice sectors + buffer sectors + emptiness of the central disk). Both are worked out carefully; the probability calculations for a sector being nice and for the buffer events are tracked with Poisson and Chernoff bounds, and the independence across disjoint buffer sectors is explicit. The embedding-aware algorithms (tiling + bottom-up merge for matching) give a further exponential improvement when coordinates are known, which is a nice bonus and shows the lower bound is model-sensitive.\n\nThe soft spots are minor and technical. The free parameters (activation thresholds log^4 n, log^{3/2} n, tiling constant 40) are chosen with hindsight and the constants are loose, but they only affect the Õ notation. The lower-bound transfer (Lemma 24) relies on the trees being placed far enough from the cut-edge that an r-round view with r < h/200 never sees it; that placement is engineered into the construction and the general round-elimination statement in the appendix absorbs the 2p error probability without changing the asymptotics. Nothing load-bearing looks broken.\n\nThis is for people who work on distributed graph algorithms or geometric random graphs. The structural theorem on trees is of independent interest even if you never care about MIS. It deserves a serious referee; the proofs are complete and checkable line-by-line. I would accept it for peer review and would cite the tree-embedding result and the complexity separation myself.","headline":"Solid, self-contained complexity separation for MIS/MM on HRGs: new geometric shattering upper bounds and a tree-embedding lower bound that cleanly separates them from 2-round colouring.","tokens_in":62865,"tokens_out":533,"would_cite":true,"duration_ms":10260,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"MIS and maximal matching stay super-constant on hyperbolic random graphs, even though colouring collapses to two rounds.","keywords":["hyperbolic random graphs","maximal independent set","maximal matching","LOCAL model","CONGEST model","geometric shattering","distributed symmetry breaking","d-ary trees"],"falsifier":"Either exhibit an o(log log n / log log log n)-round randomised LOCAL algorithm that succeeds with high probability on the giant component of every sufficiently large threshold hyperbolic random graph, or prove that such graphs contain no induced d-ary trees of the claimed height and degree.","tokens_in":62927,"feed_emoji":"📈","tokens_out":711,"duration_ms":7629,"temperature":0.7,"pith_summary":"Hyperbolic random graphs are a standard generative model for power-law networks with high clustering. Prior work showed that Δ+1 colouring can be finished in only two rounds on such graphs. This paper shows that the related symmetry-breaking tasks of maximal independent set and maximal matching do not enjoy the same collapse: both still require Ω(log log n / log log log n) rounds on the giant component. The lower bound is obtained by proving that these graphs contain many large induced d-ary trees attached by a single cut edge, so classical tree lower bounds transfer. Matching upper bounds of Õ(log^{5/3} log n) rounds (LOCAL) and Õ(log^{3} log n) rounds (CONGEST) are obtained by a two-step geometric shattering procedure that isolates only polylog-size residual components. When nodes also know their hyperbolic coordinates, maximal matching further drops to O(log log log n) rounds. The contrast with colouring therefore separates the complexity of different symmetry-breaking problems even on the same realistic network model.","feed_headline":"MIS stays hard on hyperbolic random graphs","feed_subtitle":"Colouring collapses to two rounds, yet MIS and matching still need nearly log-log rounds","key_machinery":"Geometric construction of polynomially many induced d-ary trees of height Θ(log log n / log log log n) and degree Θ(log log n), each attached to the giant component by a unique cut edge at the root; these trees let classical round-elimination lower bounds on regular trees be lifted to hyperbolic random graphs.","core_discovery":"Asymptotically almost surely, any randomised LOCAL algorithm for MIS or maximal matching on the giant component of a threshold hyperbolic random graph needs Ω(log log n / log log log n) rounds, while both problems can be solved in Õ(log^{5/3} log n) LOCAL rounds (and Õ(log^{3} log n) CONGEST rounds) by constant-round geometric shattering followed by deterministic cleanup of the residual components.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Colouring falls to 2 rounds yet MIS still needs near log-log on HRGs","MIS and matching remain Ω(log log n / log log log n) hard on HRGs","HRGs admit tall d-ary trees that lift classic MIS lower bounds","Geometric shattering yields Õ(log^{5/3} log n) MIS on hyperbolic graphs","Symmetry breaking splits: colouring easy, MIS still hard on HRGs"],"cache_read_input_tokens":58624,"weakest_assumption_plain":"An algorithm that runs for fewer rounds than roughly one-hundredth of the constructed tree height cannot notice the single cut edge that joins the tree to the rest of the giant component, so the tree lower bound still applies.","fun_headline_variants_meta":{"raw":{"variants":["Colouring falls to 2 rounds yet MIS still needs near log-log on HRGs","MIS and matching remain Ω(log log n / log log log n) hard on HRGs","HRGs admit tall d-ary trees that lift classic MIS lower bounds","Geometric shattering yields Õ(log^{5/3} log n) MIS on hyperbolic graphs","Symmetry breaking splits: colouring easy, MIS still hard on HRGs"]},"model":"grok-4.5","effort":"low","cost_usd":0.007634,"raw_usage":{"total_tokens":1905,"prompt_tokens":901,"num_sources_used":0,"completion_tokens":115,"cost_in_usd_ticks":76340000,"prompt_tokens_details":{"text_tokens":901,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":889,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":901,"tokens_out":115,"duration_ms":8745,"temperature":1.0,"reasoning_tokens":889,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T04:55:40.283441+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Either exhibit an o(log log n / log log log n)-round randomised LOCAL algorithm that succeeds with high probability on the giant component of every sufficiently large threshold hyperbolic random graph, or prove that such graphs contain no induced d-ary trees of the claimed height and degree.","supporting_citations":[],"review_version":1}