The Query Complexity of Local Search and Brouwer in Rounds

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Brânzei, Simina, Li, Jiawei
Format:	Preprint
Veröffentlicht:	2020
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Query Complexity of Local Search in Rounds on General Graphs
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

Complexity of Local Search for Euclidean Clustering Problems
von: Manthey, Bodo, et al.
Veröffentlicht: (2023)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
von: Chen, Xi, et al.
Veröffentlicht: (2026)

Rounding Large Independent Sets on Expanders
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

Quantum Search with In-Place Queries
von: Holman, Blake, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
von: Balzereit, Kaja, et al.
Veröffentlicht: (2024)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
von: Grüttemeier, Niels, et al.
Veröffentlicht: (2025)

No Price Tags? No Problem: Query Strategies for Unpriced Information
von: Nadimpalli, Shivam, et al.
Veröffentlicht: (2025)

Fast Leaf-to-Ancestor Minimum Query in the Oracle Model
von: Upirvitskiy, Aleksey, et al.
Veröffentlicht: (2026)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
von: Fei, Yumou
Veröffentlicht: (2025)

The Fine-Grained Complexity of Episode Matching
von: Bille, Philip, et al.
Veröffentlicht: (2021)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
von: Focke, Jacob, et al.
Veröffentlicht: (2023)

Further Explanations on "SAT Requires Exhaustive Search"
von: Dong, Qingxiu, et al.
Veröffentlicht: (2024)

Parameterized Complexity of Vehicle Routing
von: Döring, Michelle, et al.
Veröffentlicht: (2025)

The Complexity of Finding and Counting Subtournaments
von: Döring, Simon, et al.
Veröffentlicht: (2025)

On the Parameterized Complexity of Odd Coloring
von: Bhyravarapu, Sriram, et al.
Veröffentlicht: (2025)

On the Complexity of Signed Roman Domination
von: Reddy, Sangam Balchandar
Veröffentlicht: (2025)

On the Space Complexity of Online Convolution
von: Andersson, Joel Daniel, et al.
Veröffentlicht: (2025)

Computational Complexity in Property Testing
von: Pinto Jr., Renato Ferreira, et al.
Veröffentlicht: (2025)

A New Information Complexity Measure for Multi-pass Streaming with Applications
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

On the Parameterized Complexity of Min-Sum-Radii
von: Kumar, Pankaj, et al.
Veröffentlicht: (2026)

The Complexity of Counting Small Sub-Hypergraphs
von: Bressan, Marco, et al.
Veröffentlicht: (2025)

The Complexity of Maximal Common Subsequence Enumeration
von: Buzzega, Giovanni, et al.
Veröffentlicht: (2025)

Clustering with Locally Bounded Ignorance
von: Garvardt, Jaroslav, et al.
Veröffentlicht: (2026)

Novel Complexity Results for Temporal Separators with Deadlines
von: Dondi, Riccardo, et al.
Veröffentlicht: (2025)

Streaming Complexity Separations for Dense and Sparse Graphs
von: Liu, Yang P., et al.
Veröffentlicht: (2026)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
von: Chudigiewitsch, Florian, et al.
Veröffentlicht: (2026)

Local Enumeration: The Not-All-Equal Case
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
von: Kurita, Kazuhiro, et al.
Veröffentlicht: (2025)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
von: Abu-Khzam, Faisal N., et al.
Veröffentlicht: (2024)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
von: Liu, Wei, et al.
Veröffentlicht: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
von: Lehner, Lisa, et al.
Veröffentlicht: (2025)

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
von: Kontogiannis, Andreas, et al.
Veröffentlicht: (2026)