On the black-box complexity of Sperner's Lemma

DOI10.1007/s00224-008-9121-2zbMath1187.68233arXivquant-ph/0505185OpenAlexW2046839291WikidataQ125054626 ScholiaQ125054626MaRDI QIDQ839637

Katalin Friedl, Miklos Santha, Gábor Ivanyos, Yves F. Verhoeven

Publication date: 2 September 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/quant-ph/0505185

zbMATH Keywords

deterministic algorithmquery complexityprobabilistic and quantum lower boundSperner's Lemma

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

Cites Work

• Unnamed Item
• On total functions, existence theorems and computational complexity
• Local optimization on graphs
• Sperner's lemma and robust machines
• The relative complexity of NP search problems
• On the complexity of the parity argument and other inefficient proofs of existence
• A Sperner lemma complete for PPA
• Dividing and conquering the square
• Polynomial degree vs. quantum query complexity
• A separator theorem for graphs of bounded genus
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum Separation of Local Search and Fixed Point Computation
• On the Complexity of 2D Discrete Fixed Point Problem
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• Rapid solution of problems by quantum computation
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• On the Power of Quantum Computation
• Strengths and Weaknesses of Quantum Computing
• Quantum lower bounds by polynomials
• Mod 2 degree and a generalized No Retraction Theorem
• Lower Bounds for Local Search by Quantum Arguments
• Fundamentals of Computation Theory
• Simplicial maps from an orientable n-pseudomanifold into Sm with the octahedral triangulation
• Quantum and classical query complexities of local search are polynomially related