Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs

DOI10.1007/978-3-540-85363-3_31zbMath1159.68563OpenAlexW1927482632MaRDI QIDQ3541808

Alexander Russell, Hang Dinh

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_31

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Enhanced algorithms for local search
• Minimization algorithms and random walk on the d-cube
• Local optimization on graphs
• New upper and lower bounds for randomized and quantum local search
• Lower bounds for local search by quantum arguments
• Quantum lower bounds by quantum arguments
• Quantum and classical query complexities of local search are polynomially related

This page was built for publication: Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs