2 papers
quant-ph2005
Enhanced algorithms for Local Search
Yves F. Verhoeven
Let G=(V,E) be a finite graph, and f:V->N be any function. The Local Search problem consists in finding a local minimum of the function f on G, that is a vertex v such that f(v) is…
quant-ph2005
On the black-box complexity of Sperner's Lemma
Katalin Friedl, Gabor Ivanyos, Miklos Santha +1
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 ps…