14 citations · 69 across the 19 of their papers we have counts for
23 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 Time-Space Tradeoffs for Exponential Dynamic Programming
Susanna Caroppo, Jevgēnijs Vihrovs, Dārta Zajakina +1
We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problem…
Quantum Search on Computation Trees
Jevgēnijs Vihrovs
We show a simple generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC 2018) to the case where vertices can have different times of comput…
Boolean Functions with Minimal Spectral Sensitivity
Krišjānis Prūsis, Jevgēnijs Vihrovs
We show examples of total Boolean functions that depend on variables and have spectral sensitivity , which is asymptotically minimal. Our main new function co…
Quantum algorithms for Hopcroft's problem
Vladimirs Andrejevs, Aleksandrs Belovs, Jevgēnijs Vihrovs
In this work we study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. Given points and lines in the plane, the task is t…
Improved Algorithm and Lower Bound for Variable Time Quantum Search
Andris Ambainis, Martins Kokainis, Jevgēnijs Vihrovs
We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable tim…