Research map / Graph learning / Graph algorithms and clustering

The Query Complexity of Local Search in Rounds on General Graphs

NeurIPS 2026 · Graph learning › Graph algorithms and clustering · approach: Graph comparison and random features · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a deterministic separator-based algorithm for finding a local minimum in t rounds on general graphs with query complexity O(t n^{1/t}(sΔ)^{1-1/t}), a randomized Ω(t n^{1/t} − t) lower bound via a spanning-tree distance construction, and a parallel steepest-descent randomized upper bound.

Problem

Query complexity of finding a local minimum on a general graph when the algorithm may only make t adaptive rounds of batched oracle queries.

Approach

Recursive (t-1)-level separator decomposition (shattering lemma) gives a t-round deterministic algorithm whose query count is balanced via AM-GM over level sizes; the lower bound fixes a spanning tree and uses a sign-based distance function family with a signature lemma to bound branching per round.

Key results

• Deterministic t-round upper bound O(t n^{1/t} (sΔ)^{1-1/t}) for any graph, capped at n.
• Randomized t-round lower bound Ω(t n^{1/t} − t) for any connected graph.
• Parallel steepest descent gives O(n/(t log_Δ n) + tΔ²√n) randomized queries for Δ≥3, and O(√n + t) for Δ≤2.

Surprising findings

• Linear lower bounds do not hold for local search in two rounds on constant-degree expanders, per the parallel steepest descent algorithm.

Limitations

• Upper and lower bounds do not match in general (deterministic upper vs randomized lower bounds).
• Deterministic bound is trivial (n) when 3sΔ ≥ n.
• Lower bound is randomized while upper bound is deterministic; no matching bounds.

Experimental setup

Metrics: query complexity number of rounds

Baselines: Branzei and Li grid algorithms steepest descent with warm start

Builds on: steepest descent with a warm start (Aldous) shattering lemma / separator theory (Santha and Szegedy) Branzei and Li grid round-complexity analysis Yao's minimax principle

Closest papers by meaning

• A Near Linear Query Lower Bound for Submodular Maximization (ICML 2025 · similarity 0.86)
• Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.86)
• On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.85)
• Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.85)
• Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.85)
• On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.85)