35 citations · 98 across the 9 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.CC2017
All Classical Adversary Methods are Equivalent for Total Functions
Andris Ambainis, Martins Kokainis, Krišjānis Prūsis +2
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $\text{…
quant-ph2017★ 30 cited
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
Andris Ambainis, Martins Kokainis
We study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. That is, we are given the root of the tree and a…