Image de couverture de livre

The Query Complexity of Local Search in Rounds on General Graphs

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Brânzei, Simina, Panageas, Ioannis, Paparas, Dimitris
Format:	Preprint
Publié:	2026
Sujets:	Computational Complexity Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

The Query Complexity of Local Search and Brouwer in Rounds
par: Brânzei, Simina, et autres
Publié: (2020)

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
par: Kontogiannis, Andreas, et autres
Publié: (2026)

Complexity of Local Search for Euclidean Clustering Problems
par: Manthey, Bodo, et autres
Publié: (2023)

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
par: Anagnostides, Ioannis, et autres
Publié: (2023)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
par: Chen, Xi, et autres
Publié: (2026)

Rounding Large Independent Sets on Expanders
par: Bafna, Mitali, et autres
Publié: (2024)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
par: Grüttemeier, Niels, et autres
Publié: (2025)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
par: Greilhuber, Jakob, et autres
Publié: (2025)

Streaming Complexity Separations for Dense and Sparse Graphs
par: Liu, Yang P., et autres
Publié: (2026)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
par: Chudigiewitsch, Florian, et autres
Publié: (2026)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
par: Khanna, Sanjeev, et autres
Publié: (2026)

Quantum Search with In-Place Queries
par: Holman, Blake, et autres
Publié: (2025)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
par: Focke, Jacob, et autres
Publié: (2022)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
par: Esmer, Barış Can, et autres
Publié: (2022)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
par: Balzereit, Kaja, et autres
Publié: (2024)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
par: Dvořák, Pavel, et autres
Publié: (2022)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
par: Focke, Jacob, et autres
Publié: (2023)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
par: Assadi, Sepehr, et autres
Publié: (2024)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
par: Firbas, Alexander, et autres
Publié: (2024)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
par: Upirvitskiy, Aleksey, et autres
Publié: (2026)

No Price Tags? No Problem: Query Strategies for Unpriced Information
par: Nadimpalli, Shivam, et autres
Publié: (2025)

Generalized Graph Packing Problems Parameterized by Treewidth
par: Esmer, Barış Can, et autres
Publié: (2025)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
par: Fei, Yumou
Publié: (2025)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
par: Mu, Ta-Yu, et autres
Publié: (2024)

Further Explanations on "SAT Requires Exhaustive Search"
par: Dong, Qingxiu, et autres
Publié: (2024)

Parameterized Complexity of Vehicle Routing
par: Döring, Michelle, et autres
Publié: (2025)

The Complexity of Finding and Counting Subtournaments
par: Döring, Simon, et autres
Publié: (2025)

On the Parameterized Complexity of Odd Coloring
par: Bhyravarapu, Sriram, et autres
Publié: (2025)

On the Complexity of Signed Roman Domination
par: Reddy, Sangam Balchandar
Publié: (2025)

On the Space Complexity of Online Convolution
par: Andersson, Joel Daniel, et autres
Publié: (2025)

Computational Complexity in Property Testing
par: Pinto Jr., Renato Ferreira, et autres
Publié: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
par: Moroie, Gregory
Publié: (2025)

The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
par: Caragiannis, Ioannis, et autres
Publié: (2026)

On the Parameterized Complexity of Min-Sum-Radii
par: Kumar, Pankaj, et autres
Publié: (2026)

The Fine-Grained Complexity of Episode Matching
par: Bille, Philip, et autres
Publié: (2021)

The Complexity of Counting Small Sub-Hypergraphs
par: Bressan, Marco, et autres
Publié: (2025)

The Complexity of Maximal Common Subsequence Enumeration
par: Buzzega, Giovanni, et autres
Publié: (2025)

Clustering with Locally Bounded Ignorance
par: Garvardt, Jaroslav, et autres
Publié: (2026)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
par: Döring, Simon, et autres
Publié: (2024)