13 citations · 13 across the 3 of their papers we have counts for
6 papers
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…
Quantum Algorithms for the Triangle Problem
Frederic Magniez, Miklos Santha, Mario Szegedy
We present two new quantum algorithms that either find a triangle (a copy of ) in an undirected graph on nodes, or reject if is triangle free. The first algorith…
Quantum testers for hidden group properties
Katalin Friedl, Frederic Magniez, Miklos Santha +1
We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in t…
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…
A decision procedure for well-formed linear quantum cellular automata
Christoph Durr, Huong LeThanh, Miklos Santha
In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since i…
Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates
Wim van Dam, Frederic Magniez, Michele Mosca +1
We consider the design of self-testers for quantum gates. A self-tester for the gates F_1,...,F_m is a classical procedure that, given any gates G_1,...,G_m, decides with high prob…