10 citations · 11 across the 3 of their papers we have counts for
3 papers
cs.DS2020★ 10 cited
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…
quant-ph2019★ 1 cited
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…
quant-ph2015
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…