10 citations · 32 across the 9 of their papers we have counts for
11 papers
Certification complexity of Boolean functions
Chandrima Kayal, Sophie Laplante, Émile Larroque +2
Certificate complexity is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the va…
Quantum speedups for treewidth
Vladislavs Kļevickis, Krišjānis Prūsis, Jevgēnijs Vihrovs
In this paper, we study quantum algorithms for computing the exact value of the treewidth of a graph. Our algorithms are based on the classical algorithm by Fomin and Villanger (Co…
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 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…
All Classical Adversary Methods are Equivalent for Total Functions
Andris Ambainis, Martins Kokainis, Krišjānis Prūsis +2
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $\text{…
Zero-Error Affine, Unitary, and Probabilistic OBDDs
Rishat Ibrahimov, Kamil Khadiev, Krisjanis Prusis +2
We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreo…
Exact Affine Counter Automata
Masaki Nakanishi, Kamil Khadiev, Krišjānis Prūsis +2
We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a la…
Doubling the Success of Quantum Walk Search Using Internal-State Measurements
Krišjānis Prūsis, Jevgēnijs Vihrovs, Thomas G. Wong
In typical discrete-time quantum walk algorithms, one measures the position of the walker while ignoring its internal spin/coin state. Rather than neglecting the information in thi…
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…
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
Andris Ambainis, Krišjānis Prūsis
Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy, is wheth…