10 citations · 12 across the 2 of their papers we have counts for
5 papers
Quantum speedups for treewidth
Vladislavs Kļevickis, Krišjānis Prūsis, Jevgēnijs Vihrovs
In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Co…
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
Andris Ambainis, Kaspars Balodis, Jānis Iraids +6
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a d…
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…
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…
Sensitivity versus Certificate Complexity of Boolean Functions
Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs
Sensitivity, block sensitivity and certificate complexity are basic complexity measures of Boolean functions. The famous sensitivity conjecture claims that sensitivity is polynomia…