Tight Bounds for Randomized and Quantum Local Search

DOI10.1137/06066775XzbMath1194.68119OpenAlexW2070060459MaRDI QIDQ3575155

Shengyu Zhang

Publication date: 7 July 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/06066775x

zbMATH Keywords

optimizationlocal searchrandomized algorithmquantum algorithmquantum query complexityrandomized decision tree complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (3)

TFNP: An Update ⋮ Query complexity of approximate equilibria in anonymous games ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

This page was built for publication: Tight Bounds for Randomized and Quantum Local Search