10 citations · 12 across the 3 of their papers we have counts for
6 papers
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 the Inner Product Predicate and a Generalization of Matching Vector Families
Balthazar Bauer, Jevgēnijs Vihrovs, Hoeteck Wee
Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors.…
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…
Quadratically Tight Relations for Randomized Query Complexity
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck +5
Let be a Boolean function. The certificate complexity is a complexity measure that is quadratically tight for the zero-error randomized que…
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…