On the black-box complexity of Sperner's Lemma

DOI10.1007/S00224-008-9121-2zbMATH Open1187.68233arXivquant-ph/0505185OpenAlexW2046839291WikidataQ125054626 ScholiaQ125054626MaRDI QIDQ839637FDOQ839637

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

Publication date: 2 September 2009

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

Abstract: We present several results on the complexity of various forms of Sperner's Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an $O(sqrtn)$ deterministic query algorithm for the black-box version of the problem {�f 2D-SPERNER}, a well studied member of Papadimitriou's complexity class PPAD. This upper bound matches the $Omega(sqrtn)$ deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an $Omega(sqrt[4]n)$ lower bound for its probabilistic, and an $Omega(sqrt[8]n)$ lower bound for its quantum query complexity, showing that all these measures are polynomially related.

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

Recommendations

• Fundamentals of Computation Theory
• Logical Approaches to Computational Barriers
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• On the complexity of 2D discrete fixed point problem
• A Sperner lemma complete for PPA

zbMATH Keywords

query complexitydeterministic algorithmprobabilistic 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)

Cites Work

• On the Power of Quantum Computation
• Strengths and Weaknesses of Quantum Computing
• Rapid solution of problems by quantum computation
• On the complexity of the parity argument and other inefficient proofs of existence
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• On total functions, existence theorems and computational complexity
• The relative complexity of NP search problems
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum lower bounds by polynomials
• A separator theorem for graphs of bounded genus
• Polynomial degree vs. quantum query complexity
• On the Complexity of 2D Discrete Fixed Point Problem
• Title not available (Why is that?)
• Local optimization on graphs
• Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
• Sperner's lemma and robust machines
• A Sperner lemma complete for PPA
• Dividing and conquering the square
• Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
• Quantum Separation of Local Search and Fixed Point Computation
• 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

Cited In (6)

• Hardness of continuous local search: query complexity and cryptographic lower bounds
• On the query complexity of black-peg AB-mastermind
• Fundamentals of Computation Theory
• Some results on complexity of \(\mu\)-calculus evaluation in the black-box model
• Logical Approaches to Computational Barriers
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma

This page was built for publication: On the black-box complexity of Sperner's Lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q839637)