10 citations · 11 across the 4 of their papers we have counts for
4 papers · 1 filter
A note about claw function with a small range
Andris Ambainis, Kaspars Balodis, Jānis Iraids
In the claw detection problem we are given two functions and (, ), and we have to determine if there is exist such th…
Quantum Lower Bounds for 2D-Grid and Dyck Language
Andris Ambainis, Kaspars Balodis, Jānis Iraids +2
We show quantum lower bounds for two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of…
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…
Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection
Kaspars Balodis, Jānis Iraids
We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quant…