31 citations · 199 across the 33 of their papers we have counts for
3 papers · 1 filter
Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness
Chris Cade, Ashley Montanaro, Aleksandrs Belovs
We study space and time efficient quantum algorithms for two graph problems -- deciding whether an -vertex graph is a forest, and whether it is bipartite. Via a reduction to the…
Separations in communication complexity using cheat sheets and information complexity
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David +5
While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these meas…
Can one quantum bit separate any pair of words with zero-error?
Aleksandrs Belovs, Juan Andres Montoya, Abuzer Yakaryılmaz
Determining the minimum number of states required by a finite automaton to separate a given pair of different words is an important problem. In this paper, we consider this problem…