{"id":"e47dfa53-19a1-41f8-aa3b-cd8ddc8fbab0","arxiv_id":"2607.09626","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Stacking of Rosenbaum–Suomela base LCLs yields LCLs of randomized VOLUME/LCA probe complexity Θ(log^k n) and ˜Θ(n^{p/q}) on bounded-degree graphs and trees.","lead":"The paper constructs LCL problems whose probe complexity in LCA and VOLUME models is exactly Θ(log^k n) or ˜Θ(n^{p/q}) for any k and rational p/q. This densifies the known complexity landscape for local computation of constant-degree CSPs.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The central claims (Theorems 1–2) rest on two matching pairs of constructions. The lower-bound distributions are engineered precisely so that the root output bit is invariant under every legal choice of direction/color labels; the bijections of Lemmas 22/56 then make any o(target-complexity) probe set information-theoretically useless for predicting that bit. Because those lemmas already neutralize the adaptive-labeling worry raised by the reader, the Yao-minimax argument goes through. The upper bounds follow by stacking the known random-walk / hierarchical sampling algorithms of Rosenbaum–Suomela and verifying the four “strong-algorithm” invariants by induction on tree depth; the calculations (especially the probe-budget arithmetic around Eqs. (9)–(10) and (12)–(13)) check out. Residual length and AI-assisted proof text introduce only ordinary human-verification risk, not a structural flaw. Consequently the reader’s ACCEPT verdict stands.","tokens_in":45089,"tokens_out":517,"duration_ms":6190,"concrete_test":"Independently re-derive the base case and one inductive step of the bijection in Lemma 25 (sequence length 2) and of the corresponding step in Lemma 56 (T with val(T)=2/3), confirming that flipping the designated auxiliary bit always flips b_I while preserving every input bit outside an o(target) vertex set; if either step fails, the Yao argument collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest-assumption concern about adaptive direction/color labels is already closed by the paper's own construction. Lemmas 22 and 56 build hard distributions in which every legal global solution is forced to output a fixed root bit b_I independent of the algorithm's choice of d/c_out labels (via the recursive xor-twisting of auxiliary bits and the bijections that preserve any o(target-complexity) set of input bits). The inductive arguments establishing those bijections (Lemma 25 for the polylog case, the induction on |T| for the polynomial case) appear complete and do not leave residual freedom for an adaptive labeling to correlate the root bit with unprobed inputs. The upper-bound algorithms (SolvePTL^k and the strong-algorithm induction for SolveHC_T) are likewise self-contained and match the claimed bounds. No other load-bearing gap that would undermine Theorems 1–2 is apparent.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper constructs new LCL complexity classes for randomized local computation algorithms (LCAs) and the VOLUME model. Using a stacking technique on base constructions of Rosenbaum–Suomela (LeafColoring / path-to-leaf and Hierarchical-THC), it proves that for every integer k≥1 there is an LCL with probe complexity Θ(log^k n) (Theorem 1, via Π^k_PTL), and for every rational x∈(0,1] there is an LCL with probe complexity ˜Θ(n^x) (Theorem 2, via Π^T_HC parameterized by the value of a good ordered binary tree T). Both upper and lower bounds hold for VOLUME and LCA, and on both bounded-degree graphs and trees. Upper bounds are explicit Las-Vegas algorithms (random walks, binary lifting, recursive “strong” algorithms) converted to Monte Carlo; lower bounds use hard distributions that force a fixed root output bit independent of direction/color choices, combined with Yao’s principle and inductive bijections that preserve any o(target-complexity) set of input bits.","tokens_in":45358,"tokens_out":842,"duration_ms":22850,"significance":"The work answers two explicit open questions of Rosenbaum–Suomela on the density of randomized VOLUME complexities in the polylogarithmic and polynomial regimes, and simultaneously transfers the landscape to the LCA model and to trees. The stacking method is technically distinct from the Turing-machine encodings used for dense LOCAL complexities, and yields a clean, combinatorial explanation of how probe complexity can be finer-grained than distance complexity on trees. Explicit algorithms, matching hard distributions, and inductive arguments that close the adaptive-labeling loophole are genuine strengths; the results are therefore a solid, self-contained contribution to the complexity classification of LCLs under probe-based models.","major_comments":[],"minor_comments":[{"comment":"Definition 40 (strong algorithm) is the technical heart of the polynomial upper bound; a short informal paragraph immediately before it, summarizing the roles of N1 (ideal size), N2 (maximum size) and the two probe bounds (12)–(13), would make the subsequent induction far easier to follow.","section":null},{"comment":"In §4.2–4.3 and §5.3–5.5 the inductive arguments are long and were partly AI-assisted. Adding a one-sentence “proof roadmap” at the start of each major lemma (especially Lemmas 25, 47, 52 and 56) would improve human readability without changing the mathematics.","section":null},{"comment":"Figure 1 and Figure 2 are helpful, but the caption of Figure 2 should explicitly state that the solid blue segment covers every rational exponent, not merely a dense set of reals.","section":null},{"comment":"Notation for ports (P, LC, RC, NC / DC) is overloaded between the multi-level binary-tree labeling and the T-labeling; a brief table or a consistent subscript convention would reduce cognitive load.","section":null},{"comment":"Remark 8 (Las Vegas → Monte Carlo) is standard but should cite the precise success-probability budget used later (1−1/n or 1−n*/n^{2}) so that the conversion is fully mechanical.","section":null},{"comment":"Section 6.2 correctly leaves open the polynomial separation of LCA versus VOLUME; a one-sentence pointer to the connectivity-reduction of Göös et al. already cited as [30] would make the remaining randomness question sharper.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The AI-assistance disclosure is transparent and the author accepts full responsibility; I see no integrity issue. The technical core appears sound on a careful reading, so the request for minor revision is purely for presentation and human-checkability of the long inductive arguments, not for any load-bearing gap."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper does what it claims: it produces LCLs with randomized probe complexity Θ(log^k n) for every k and ˜Θ(n^x) for every rational x in (0,1], in both VOLUME and LCA, on bounded-degree graphs and trees. That closes the two explicit open questions left by Rosenbaum–Suomela (2020).\n\nWhat is new is the stacking technique itself. Instead of the Turing-machine encodings used for LOCAL density, Peng takes the known Θ(log n) LeafColoring / path-to-leaf base and the ˜Θ(n^{1/k}) Hierarchical-THC base and stacks them in two different ways—one that forces the algorithm to solve every attached copy along a path, one that forces it to solve only one carefully chosen copy. The polylog construction is clean; the polynomial one is parameterized by good ordered binary trees whose values generate every rational, and the “strong algorithm” induction (ideal size + max size + binary lifting) is the technical heart that makes the upper bound work without knowing sub-instance sizes.\n\nThe lower-bound distributions are carefully built so that every legal global solution is forced to a fixed root bit b_I no matter how the algorithm chooses directions or colors. The inductive bijections that preserve any o(target) set of input bits look complete; the adaptive-labeling worry the reader flagged is already closed by the construction. Upper bounds are explicit Las-Vegas algorithms converted to Monte-Carlo by the usual budget cut-off. Citation pattern is appropriate and the base cases are taken from published work.\n\nSoft spots are real but secondary. The proofs are long, heavily inductive, and the author notes AI assistance on Sections 4–5; that raises ordinary verification cost, not a soundness hole. The VOLUME-to-LCA transfer is only one direction (Observation 7), so the models are not shown equivalent, but the paper never claims they are. No free parameters, no circularity.\n\nThis is for people who care about the fine structure of LCL complexity landscapes in probe models. It deserves a serious referee. I would accept it for peer review and would cite the constructions when I next need a dense family of probe lower bounds.","headline":"Solid stacking construction that fills the open polylog and rational-polynomial slots for VOLUME/LCA LCLs, answering Rosenbaum–Suomela directly.","tokens_in":45904,"tokens_out":539,"would_cite":true,"duration_ms":7779,"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":"Stacking known LCL gadgets produces every polylog and every rational polynomial probe complexity for local computation algorithms.","keywords":["local computation algorithms","VOLUME model","locally checkable labeling","probe complexity","complexity landscape","stacking constructions"],"falsifier":"Exhibit either a randomized LCA that solves one of the stacked problems with o(log^k n) (respectively o(n^x / polylog n)) probes on the hard tree family, or a proof that every legal solution on that family can make the root bit depend on the unprobed input bits once intermediate labels are chosen adaptively.","tokens_in":46045,"feed_emoji":"📐","tokens_out":601,"duration_ms":7438,"temperature":0.7,"pith_summary":"Local computation algorithms must answer queries about a consistent global solution to a massive graph problem while probing only a tiny portion of the input. Restricting attention to locally checkable labeling problems—constant-degree constraint-satisfaction problems whose solutions can be verified by looking at constant-radius neighborhoods—lets one ask a clean complexity-classification question: which probe-complexity functions actually arise? The paper answers that question for two natural regimes. By recursively stacking copies of two base constructions already known to require Θ(log n) and roughly n^{1/k} probes, it produces new LCLs whose randomized probe complexity is exactly Θ(log^k n) for every positive integer k and roughly n^x for every rational x between 0 and 1. The same bounds hold both for ordinary LCAs and for the more restricted VOLUME model, and they hold already on trees. The constructions therefore fill previously empty intervals of the complexity landscape and show that probe complexity can be far denser than the round-complexity landscape of the classical LOCAL model on the same problems.","feed_headline":"Every polylog and rational power arises as LCA probe complexity","feed_subtitle":"Stacking two base LCL gadgets fills the missing slots on trees and general graphs","key_machinery":"Stacking of base VOLUME gadgets (path-to-leaf and hierarchical two-coloring instances): each vertex of a higher-level instance is given a “twisted” input bit that is the XOR of a local bit and the root-output bit of a fresh lower-level copy; forcing the algorithm to solve all (or one carefully chosen) of those copies multiplies the probe cost and produces the desired exponents.","core_discovery":"There exist LCL problems whose randomized probe complexities, in both the LCA and VOLUME models, are Θ(log^k n) for every positive integer k and ˜Θ(n^x) for every rational x in (0,1], already when the input is restricted to bounded-degree trees.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["All polylog and rational powers arise as LCA probe complexities","Stacking base LCL gadgets fills every polylog and n^{p/q} slot","LCLs exist with Θ(log^k n) and ˜Θ(n^{p/q}) probe costs in LCAs","Bounded-degree trees admit every polylog and rational LCA complexity","VOLUME and LCA models realize all log powers and rational exponents"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The hard distributions are built so that every legal global solution must output one fixed bit at a designated root, no matter how the algorithm chooses intermediate direction or color labels.","fun_headline_variants_meta":{"raw":{"variants":["All polylog and rational powers arise as LCA probe complexities","Stacking base LCL gadgets fills every polylog and n^{p/q} slot","LCLs exist with Θ(log^k n) and ˜Θ(n^{p/q}) probe costs in LCAs","Bounded-degree trees admit every polylog and rational LCA complexity","VOLUME and LCA models realize all log powers and rational exponents"]},"model":"grok-4.5","effort":"low","cost_usd":0.006214,"raw_usage":{"total_tokens":1681,"prompt_tokens":872,"num_sources_used":0,"completion_tokens":88,"cost_in_usd_ticks":62140000,"prompt_tokens_details":{"text_tokens":872,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":721,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":872,"tokens_out":88,"duration_ms":6866,"temperature":1.0,"reasoning_tokens":721,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-13T01:38:06.849753+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit either a randomized LCA that solves one of the stacked problems with o(log^k n) (respectively o(n^x / polylog n)) probes on the hard tree family, or a proof that every legal solution on that family can make the root bit depend on the unprobed input bits once intermediate labels are chosen adaptively.","supporting_citations":[],"review_version":1}