10 citations · 19 across the 11 of their papers we have counts for
14 papers
An Optimal Separation Between Certificate Complexity and Approximate Degree
Kaspars Balodis
We prove that certificate complexity can be quartically larger than approximate degree. More precisely, we construct a family of total Boolean functions with $$ C(G) = \tildeΩ(…
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…
Several Separations Based on a Partial Boolean Function
Kaspars Balodis
We show a partial Boolean function together with an input such that both and are at leas…
Unambiguous DNFs and Alon-Saks-Seymour
Kaspars Balodis, Shalev Ben-David, Mika Göös +2
We exhibit an unambiguous k-DNF formula that requires CNF width , which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the…
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…
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…