2 papers
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…
quant-ph2001
Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem
Gabor Ivanyos, Frederic Magniez, Miklos Santha
In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden…