{"id":"8da45ded-cc04-495a-b5b5-6b8ecd9e34dc","arxiv_id":"2505.00915","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Non-adaptive LCAs for constant approximations of matching and vertex cover require Δ^{Ω(log Δ / log log Δ)} queries, so the Parnas-Ron black-box reduction is optimal up to exponents.","lead":"This paper proves that any non-adaptive local computation algorithm for constant-factor maximum matching, minimum vertex cover, or maximal independent set must make Δ^{Ω(log Δ / log log Δ)} queries, matching the long-standing Parnas-Ron upper bound. It is the first separation between adaptive and non-adaptive local computation algorithms, and it closes off a proposed route to faster massively parallel matching algorithms.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The degree-only WLOG after Claim 5.4 is not justified: the model gives the LCA actual vertex identities, and the proof bounds total variation of degree sequences, not of the full observed query tree. This gap is load-bearing for Claim 5.1.","rationale":"I read the paper in good faith: the main matching lower bound is a serious and plausible result, and the KMW-based construction with dummy clusters and the coupling over label sequences is a meaningful technical contribution. The reader's conditional verdict is appropriate. The load-bearing weakness is the unproved reduction from the algorithm's actual observation to a degree sequence. The proof correctly identifies that the explored subgraph is a tree with high probability, but from 'tree' it does not follow that the output depends only on degrees; the query instructions plus the equality pattern of returned vertices determine the explored tree, and labels can carry that pattern. The coupling in Claim 5.7 tracks one-step backtracking for path-level coupling, but the overall argument still bounds only degree-sequence total variation. If the full query-tree type has total variation much larger than O(1/kappa), then a label-using LCA could distinguish significant from misleading edges even when degree sequences are close, and Claim 5.1 would not follow. This is not an internal contradiction, and a strengthened coupling may well exist; for that reason I do not recommend rejection or unverdictable status. The right outcome is conditional acceptance, with the condition that the authors either replace the degree-only WLOG by a proof for the full observed query tree or formally justify that vertex labels are independent noise in a way that makes the degree sequence sufficient. The proposed concrete check targets exactly this missing step and would settle whether the concern lands.","tokens_in":28928,"tokens_out":35480,"duration_ms":404217,"concrete_test":"Re-derive Claim 5.8 with the random variable defined as the full isomorphism type of the explored query tree, including which query positions map to the same graph vertex, and prove a coupling of these full observations that fails with probability O(1/kappa). A minimal check: for a query tree consisting of a root, a child, and a grandchild query, compute the distribution of the event 'the grandchild query returns the root' under significant and misleading starts; verify whether the label-based coupling of Claim 5.7 couples this event with probability 1 - O(1/kappa^2). If the coupling can only be shown for degree sequences but not for the equality pattern, then the degree-only WLOG fails and Claim 5.1 needs a new argument.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central proof reduces the algorithm's observation to a degree sequence. Immediately after Claim 5.4 the paper says: 'we can assume without loss of generality that the algorithm computes the output based on the sequence of degrees.' But Definition 3.1 gives the LCA the vertices returned by adjacency-list queries, so a real algorithm may use vertex labels and, in particular, equality patterns among returned vertices. The coupling in Claim 5.7 bounds the probability that the degree sequences on a path differ; Claim 5.8 then bounds the total variation of the whole degree sequence. This does not control the total variation of the labeled or even the unlabeled query tree, because two explorations can have identical degree sequences while differing in which query positions map to the same graph vertex. The 'special edges' paragraph in Claim 5.7 acknowledges that one-step backtracking must be tracked separately, but the reduction to degrees is still asserted, not proved. Without a proof that the full observed query-tree type has total variation O(1/kappa) between significant and misleading starts, the transfer from mislead-edge probabilities to significant-edge probabilities in Claim 5.1 is unsupported. The concern is about an unproved reduction, not an observed contradiction; the result may be repairable, but the current text does not supply the needed argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper formalizes non-adaptive LCAs and proves a lower bound of Δ^{Ω(log Δ / log log Δ)} queries for any non-adaptive LCA that with constant probability computes an O(1)-approximation of maximum matching or minimum vertex cover, or a maximal independent set, where Δ is the maximum degree. The proof constructs a hard distribution based on a modified Kuhn-Moscibroda-Wattenhofer cluster-tree construction, adds dummy clusters to kill very long walks, and uses couplings over acyclic explored subgraphs in the style of recent sublinear-time lower bounds. The paper also proves a conditional result showing that a non-adaptive MVC LCA with query complexity Δ^{(log Δ)^{1-ε}} would yield an MPC algorithm for approximate maximum matching in (log n)^{1/2-Ω(ε)} rounds, and interprets Theorem 1.1 as ruling out that route.","tokens_in":29186,"tokens_out":12098,"duration_ms":127650,"significance":"If the lower bound is correct, it is the first separation between adaptive and non-adaptive LCAs for these problems, it matches the Parnas-Ron upper bound up to constants in the exponent, and it closes a concrete avenue toward improved MPC algorithms. The combination of the KMW cluster-tree construction with coupling-based sublinear-time lower bound techniques is a genuine technical contribution. The main caveat is that the proof as written contains a load-bearing reduction to degree-only observations that is not formally justified, and the MIS section is only a sketch; both need to be completed before the result can be considered established.","major_comments":[{"comment":"The reduction to degree-only observation is not justified and is load-bearing. Definition 3.1 gives the algorithm the actual vertices returned by adjacency-list queries, so a non-adaptive LCA may use equality patterns among returned vertices, in particular whether a query returns the parent vertex. Claim 5.4 only shows that the induced subgraph on discovered vertices is a tree; it does not imply that the degree sequence determines the full observed query tree, because two explorations can have identical degree sequences while disagreeing on which query positions map to the same graph vertex. Claim 5.8 bounds the total variation of the degree sequence only, while Claim 5.1 transfers this to output probabilities, which requires the output to be a function of the degree sequence. The sentence \"we can assume without loss of generality\" after Claim 5.4 is the only support for this step, and it is not implied by the preceding claims. Please provide a formal proof that restricting to degree sequences is without loss, or strengthen the coupling to bound the total variation of the fully labeled observed query tree, including equality patterns.","section":"§5, paragraph after Claim 5.4"},{"comment":"The proof defers a \"careful treatment\" of revisiting vertices, but this is exactly the place where the degree sequence fails to determine the observed query tree. The sketched fix asserts that special edges are traversed with probability at most 1/Δ, that special edges do not appear inside identical subtrees, and that traversing a special edge increases the maximum color by at most 1, and then asserts the coupling fails with probability at most 2/κ^2. These assertions are not proved, and the probability bound needs a careful accounting over all steps because the special edge is chosen from the remaining outgoing edges after one edge of a given label has been removed. Please supply the full proof of the special-edge handling, or otherwise prove that the coupling can be extended to the labeled query tree.","section":"§5, final paragraph of Claim 5.7"},{"comment":"The MIS lower bound is only a sketch. The text says \"it can be shown\" that the coupling maintains the invariant with probability 1-o(1), but no proof is given. This is not a routine adaptation: when the algorithm explores the line graph G' = L(G), the query graph can contain triangles corresponding to three edges sharing an endpoint in G, so the tree argument of Claims 5.3-5.4 does not apply directly to G'. The translation between queries in G' and queries in G also needs a formal treatment under the non-adaptive LCA model. Since MIS is one of the three problems in Theorem 1.1, this is load-bearing; please provide the full proof or explicitly state MIS as a corollary that depends on a completed coupling argument.","section":"§7, Theorem 7.1 and surrounding text"},{"comment":"Theorem 8.2 is stated for any non-adaptive LCA that O(1)-approximates minimum vertex cover, but the proof requires the stronger hypothesis that the LCA also outputs a matching of size within a constant of its vertex cover, as stated in Remark 8.3. As written, the implication in Theorem 8.2 does not follow from its stated hypothesis. Please restate the theorem to include the certificate assumption, or prove the implication without it. This does not affect the lower bound in Theorem 1.1, but it is the formal basis for the MPC motivation.","section":"§8, Theorem 8.2 and Remark 8.3"}],"minor_comments":[{"comment":"The title contains a typo: \"Local Computation Algorithm s\" should be \"Local Computation Algorithms\".","section":"Title/abstract"},{"comment":"The denominator in the probability of taking a critical step is written as \\bar d_r + Δ_r + 1, but Claim 4.16 states dB(C) = \\bar d_r + Δ_r + 2 for non-leaf clusters; please reconcile the discrepancy.","section":"§5, Claim 5.7"},{"comment":"The quantity ℓ = 2 log κ uses log without specifying the base; the subsequent asymptotic estimates should state the base or use asymptotic notation throughout.","section":"§5, Claim 5.7"},{"comment":"In the approximation-ratio display, the equality \"= (r+1)/(δ-(r+1)) + 2ε + o(1)\" should be an inequality \"≤\" because it follows from the upper bound on N in Claim 4.20.","section":"§5, Lemma 5.2"},{"comment":"The final sentence says \"the total size of the messages is bounded by M Q^2\" but the preceding discussion bounds per-machine and total message sizes in terms of n and Q; please check whether M should be n or clarify the notation.","section":"§8, Claim 8.8"}],"recommendation":"major_revision","confidential_remarks":"This is a potentially significant paper: the claimed separation is important, and the high-level approach of modifying the KMW construction and applying BRR-style couplings is creative. However, the degree-only reduction is a serious correctness gap in the main proof, and the MIS section is only a sketch. I would support publication if the authors can supply the missing proof of the reduction (or extend the coupling to the full labeled query tree) and complete the MIS argument. I do not see a circularity or novelty concern: the use of [8,9] is a reuse of techniques, not of results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth reading: this is the first lower bound separating non-adaptive from adaptive LCAs, and it shows the Parnas-Ron black-box reduction is tight up to exponents for MM, MVC, and MIS. The main proof blends BRR's coupling machinery with the KMW cluster construction, and the observation that any random walk on the modified KMW instance has only Delta^{-Omega(log Delta / log log Delta)} chance of hitting a distinguishing edge is genuinely new.\n\nWhat's solid: the construction is parameterized carefully, Claims 4.4-4.10 and the omitted proofs in Appendix A check out; Claim 4.14 is a clean characterization of distinguishing label sequences; Claim 5.3's two-switch argument for sparsity is standard but correctly done. The MPC application (Theorem 8.2) is explicitly conditional but a nice motivation, and Remark 8.3 is honest about the extra matching-certificate assumption. The citation pattern is clean: the BRR couplings and KMW construction are the right prior work to build on, and the self-citations are to the tools being adapted, not a circular dependency.\n\nWhere it gets soft: the paper's central reduction to degree sequences is asserted, not proved. Right after Claim 5.4 it says we can assume without loss of generality that the algorithm computes the output based on the sequence of degrees, but Definition 3.1 gives the algorithm the actual vertices, including equality patterns. Two explorations can have identical degree sequences while differing in which queries hit the parent (backtracking). The later paragraph in Claim 5.7 acknowledges this and sketches a special-edges fix, but the fix is three bullets with properties asserted and no proof; the claim formally only bounds total variation of degree sequences, while Claim 5.1 needs total variation of the full observed tree. The stress-test note is right that this is a load-bearing gap, not a stylistic one. It looks repairable, and the special-edges coupling is plausible, but the current text does not supply the argument. Section 7 (MIS) is also a sketch of a reduction to line graphs with no formal claim; that is a smaller gap because it is a reduction, but as written it is not a proof. Minor: Theorem 1.1 should state the large-n regime (Delta = 2^{O(sqrt(log n log log n))}) since the hard instance requires it.\n\nBottom line: the high-level approach is sound and the result is likely correct, but this version is not complete. A serious referee should take it, and the revision should replace the degree-only WLOG with a formal coupling of the full observed tree including repeated vertices and labels, fill in Claim 5.7's special-edges case, and give Section 7 a real proof. I would be comfortable with conditional acceptance after those changes.","headline":"Important and likely correct lower bound for non-adaptive LCAs, but the proof as written skips a load-bearing reduction from observed trees to degree sequences and leaves the MIS section as a sketch.","tokens_in":29723,"tokens_out":10446,"would_cite":true,"duration_ms":110273,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that any non-adaptive local computation algorithm that constant-approximates maximum matching or minimum vertex cover, or computes a maximal independent set, requires Δ^{Ω(log Δ / log log Δ)} queries.","keywords":["non-adaptive LCA","local computation algorithms","maximum matching","minimum vertex cover","maximal independent set","lower bound","distributed algorithms","MPC"],"falsifier":"Evaluate the paper's hard distribution at a concrete value such as Δ=$2^{{20}}$ with query count $Δ^{{0.1 log Δ / log log Δ}}$, and measure the total variation distance between the degree sequences observed from a significant edge and from a misleading edge; a constant distance would refute the central indistinguishability claim, as would any non-adaptive LCA with $Δ^{{o(log Δ / log log Δ)}}$ queries that constant-approximates maximum matching on all bounded-degree graphs.","tokens_in":28740,"feed_emoji":"📉","tokens_out":7277,"duration_ms":68460,"temperature":0.7,"pith_summary":"Local Computation Algorithms (LCAs) answer queries about a global solution by inspecting a small part of the input; a non-adaptive LCA must fix its entire probe pattern in advance. The paper proves that any LCA of this kind that constant-approximates maximum matching or minimum vertex cover, or outputs a maximal independent set, needs $Δ^{{Ω(log Δ / log log Δ)}}$ queries, where Δ is the maximum degree. This matches, up to constants in the exponent, the query count of the best known non-adaptive LCAs obtained from distributed algorithms, and it is the first separation from adaptive LCAs, which solve the same problems with poly(Δ) queries. A corollary is that a whole family of potential faster massively parallel algorithms for approximate matching—those built from non-adaptive LCAs—is ruled out.","feed_headline":"Adaptivity is provably necessary for fast local matching algorithms","feed_subtitle":"Non-adaptive local algorithms need Δ^{Ω(logΔ/loglogΔ)} queries for constant matching approximations","key_machinery":"The load-bearing object is a blueprint made of two isomorphic recursively defined cluster trees (clusters of vertices, edges labeled by degrees), a dummy cluster attached to every cluster, and a perfect matching between corresponding clusters of the two trees. The final graph is obtained by replacing each blueprint edge with a random regular bipartite graph between the two clusters. Two facts carry the argument: (1) random bipartite subgraphs make the explored subgraph a tree with high probability, so the algorithm's observation is just a degree sequence; and (2) a coupling between paths starting from a significant and a misleading edge fails only when the label sequence is distinguishing, and any distinguishing sequence must contain a subsequence of r small labels $δ^{0}$, $δ^{1}$, ..., $δ^{{r-1}}$, an event whose probability is at most (ℓ/$δ^{{(r+1)/2}}$)^r ≤ 1/$κ^{2}$. The dummy cluster guarantees that walks longer than r log Δ steps are absorbed with probability close to 1, so only moderately long walks matter.","core_discovery":"The central claim is Theorem 1.1: any possibly randomized non-adaptive LCA that returns an O(1) approximation of maximum matching, an O(1) approximation of minimum vertex cover, or a maximal independent set with constant probability requires $Δ^{{Ω(log Δ / log log Δ)}}$ queries. The proof constructs a family of graphs in which each edge is either significant (part of a large matching) or misleading (belongs to a sparse set), and shows via a coupling over the query tree that the degree sequence observed by any non-adaptive LCA is nearly the same whether the queried edge is significant or misleading. Hence a constant approximation to the maximum matching cannot include a constant fraction of significant edges without also accepting misleading edges. The same construction, with minor modifications, handles vertex cover and maximal independent set.","pith_inferences":["The dummy-cluster trick—forcing every long random walk to hit an uninformative absorbing cluster with constant probability per step—might be a general recipe for strengthening radius-based distributed lower bounds into LCA lower bounds for other local problems.","If the coupling argument can be tightened, similar lower bounds may hold for exact maximum matching or for approximation ratios below some threshold, where adaptive LCAs are also less understood.","The paper's reduction of the algorithm's view to the degree sequence suggests that non-adaptive LCA lower bounds in general graphs reduce to understanding random labeled trees; defining a canonical label-free model might simplify future lower bounds.","One could test whether the MPC consequence is the real bottleneck: the same lower bound does not rule out faster MPC algorithms built from adaptive LCAs or from direct graph sparsification, so the open MPC problem remains open but is narrowed."],"forward_implications":["The reduction from distributed algorithms to non-adaptive LCAs is optimal up to exponent constants for constant approximations of maximum matching, minimum vertex cover, and maximal independent set.","Adaptivity is strictly necessary for poly(Δ)-query LCAs for these problems: no non-adaptive algorithm can match the adaptive poly(Δ) upper bounds.","Any attempt to improve massively parallel algorithms for approximate matching cannot succeed by improving non-adaptive LCAs; the suggested LCA-to-MPC route is closed.","The lower bound holds for randomized non-adaptive LCAs as well, by the minimax principle applied to the deterministic construction.","The query-complexity threshold Δ^{Θ(log Δ / log log Δ)} is the exact frontier for non-adaptive LCAs for these problems."],"supporting_citations":[{"why":"Establishes the reduction from distributed algorithms to non-adaptive LCAs; the algorithm whose query bound this paper matches is obtained through it.","marker":"[27]"},{"why":"Supplies the two-cluster-tree hard construction for distributed lower bounds that the paper modifies into its graph distribution.","marker":"[23]"},{"why":"Introduces coupling techniques over acyclic subgraphs for sublinear-time lower bounds, adapted here to the new instance.","marker":"[8]"},{"why":"Provides the random-bipartite-subgraph argument that keeps the explored subgraph acyclic with high probability.","marker":"[9]"},{"why":"Further sublinear lower-bound framework used alongside [8,9] in the proof.","marker":"[10]"},{"why":"Gives the distributed O(log Δ / log log Δ)-round algorithm for (2+ε)-approximate vertex cover that yields the matched upper bound.","marker":"[4]"}],"fun_headline_variants":["Non-adaptive LCAs need super-polynomial queries for matching","Adaptivity provably helps local matching: separation proved","Parnas-Ron reduction is tight for non-adaptive LCAs","Optimal lower bound for non-adaptive local computation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a non-adaptive LCA's observation can be reduced to the degree sequence of the explored tree; if random vertex labels ever carried extra distinguishing information, the proof's total-variation bound would not control the algorithm's success.","fun_headline_variants_meta":{"raw":{"variants":["Non-adaptive LCAs need super-polynomial queries for matching","Adaptivity provably helps local matching: separation proved","Parnas-Ron reduction is tight for non-adaptive LCAs","Optimal lower bound for non-adaptive local computation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000408,"raw_usage":{"total_tokens":2199,"prompt_tokens":1104,"completion_tokens":1095,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":720,"completion_tokens_details":{"reasoning_tokens":1026}},"tokens_in":720,"tokens_out":1095,"duration_ms":11372,"temperature":1.0,"reasoning_tokens":1026,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:35:19.679048+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate the paper's hard distribution at a concrete value such as Δ=$2^{{20}}$ with query count $Δ^{{0.1 log Δ / log log Δ}}$, and measure the total variation distance between the degree sequences observed from a significant edge and from a misleading edge; a constant distance would refute the central indistinguishability claim, as would any non-adaptive LCA with $Δ^{{o(log Δ / log log Δ)}}$ queries that constant-approximates maximum matching on all bounded-degree graphs.","supporting_citations":[{"cited_title":"Approximating the Minimum V ertex Cover in Sublinear Time and a Connection to Distributed Algorithms","cited_arxiv_id":null,"evidence_quote":"Establishes the reduction from distributed algorithms to non-adaptive LCAs; the algorithm whose query bound this paper matches is obtained through it."},{"cited_title":"Sublinear time algorithms and complexity of approximate maximum matching","cited_arxiv_id":null,"evidence_quote":"Introduces coupling techniques over acyclic subgraphs for sublinear-time lower bounds, adapted here to the new instance."},{"cited_title":"Local computation algorithms for maximum matching: New lower bounds","cited_arxiv_id":null,"evidence_quote":"Provides the random-bipartite-subgraph argument that keeps the explored subgraph acyclic with high probability."},{"cited_title":"Approximating maximum matching requires almost quadratic time","cited_arxiv_id":null,"evidence_quote":"Further sublinear lower-bound framework used alongside [8,9] in the proof."},{"cited_title":"A distributed (2 + ε)- approximation for vertex cover in o(log ∆ / ε log log ∆) rounds","cited_arxiv_id":null,"evidence_quote":"Gives the distributed O(log Δ / log log Δ)-round algorithm for (2+ε)-approximate vertex cover that yields the matched upper bound."}],"review_version":1}