10 citations · 32 across the 9 of their papers we have counts for
Showing 2018Show all
2 papers · 1 filter
cs.CC2018
On Block Sensitivity and Fractional Block Sensitivity
Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs
We investigate the relation between the block sensitivity and fractional block sensitivity complexity measures of Boolean functions. While it is know…
quant-ph2018★ 1 cited
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
Andris Ambainis, Kaspars Balodis, Jānis Iraids +3
In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path i…