On the black-box complexity of Sperner's Lemma

DOI10.1007/S00224-008-9121-2MaRDI QIDQ839637zbMATHOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(6)

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

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)