17 citations · 34 across the 8 of their papers we have counts for
10 papers
Representing polynomial of ST-CONNECTIVITY
Jānis Iraids, Juris Smotrovs
We show that the coefficients of the representing polynomial of any monotone Boolean function are the values of the Möbius function of an atomistic lattice related to this function…
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…
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
Scott Aaronson, Andris Ambainis, Jānis Iraids +2
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function is computable by a 1-query quantum alg…
Separations in Query Complexity Based on Pointer Functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the fu…
Parameterized Quantum Query Complexity of Graph Collision
Andris Ambainis, Kaspars Balodis, Jānis Iraids +2
We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O…