Quantum and randomized lower bounds for local search on vertex-transitive graphs
From MaRDI portal
Publication:3172447
zbMATH Open1234.81054MaRDI QIDQ3172447FDOQ3172447
Authors: Hang Dinh, Alexander Russell 
Publication date: 5 October 2011
Recommendations
- Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
- Tight bounds for randomized and quantum local search
- New upper and lower bounds for randomized and quantum local search
- Lower bounds for local search by quantum arguments
- Lower Bounds for Local Search by Quantum Arguments
Searching and sorting (68P10) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)
Cited In (10)
- Lower Bounds for Local Search by Quantum Arguments
- Quantum and classical query complexities of local search are polynomially related
- Almost Envy-Freeness with General Valuations
- Tight bounds for randomized and quantum local search
- On the quantum query complexity of local search in two and three dimensions
- On the minimum degree up to local complementation: bounds and complexity
- Vertices cannot be hidden from quantum spatial search for almost all random graphs
- Lower bounds for local search by quantum arguments
- Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
- Impact of global and local interaction on quantum spatial search on chimera graph
This page was built for publication: Quantum and randomized lower bounds for local search on vertex-transitive graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3172447)
