New upper and lower bounds for randomized and quantum local search

DOI10.1145/1132516.1132605zbMath1301.68132OpenAlexW2025373303MaRDI QIDQ2931424

Shengyu Zhang

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132605

zbMATH Keywords

local searchrandomized algorithmlower boundquantum algorithmquery complexitydecision tree complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Quantum computation (81P68) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (6)

On the quantum query complexity of local search in two and three dimensions ⋮ Quantum separation of local search and fixed point computation ⋮ Evolutionary algorithms for quantum computers ⋮ Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs ⋮ Quantum and classical query complexities of local search are polynomially related ⋮ Ranking-based black-box complexity

This page was built for publication: New upper and lower bounds for randomized and quantum local search