Jevgēnijs Vihrovs | DeepAI

AI Chat

Featured Co-authors

Rahul Jain
52 publications
Kamil Khadiev
23 publications
Miklos Santha
13 publications
Troy Lee
13 publications
Andris Ambainis
10 publications
Swagato Sanyal
10 publications
Yixin Shen
7 publications
Adam Glos
7 publications
Krišjānis Prūsis
6 publications
Kaspars Balodis
6 publications
Srijita Kundu
6 publications

∙ 02/16/2022

Quantum speedups for treewidth

In this paper, we study quantum algorithms for computing the exact value...

0 Vladislavs Kļevickis, et al. ∙

∙ 04/29/2021

Quantum speedups for dynamic programming on n-dimensional lattice graphs

Motivated by the quantum speedup for dynamic programming on the Boolean ...

0 Adam Glos, et al. ∙

∙ 07/06/2020

Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

We study the quantum query complexity of two problems. First, we consi...

0 Andris Ambainis, et al. ∙

∙ 10/04/2018

On the Inner Product Predicate and a Generalization of Matching Vector Families

Motivated by cryptographic applications such as predicate encryption, we...

0 Balthazar Bauer, et al. ∙

∙ 10/04/2018

On Block Sensitivity and Fractional Block Sensitivity

We investigate the relation between the block sensitivity bs(f) and frac...

0 Andris Ambainis, et al. ∙

∙ 07/13/2018

Quantum Speedups for Exponential-Time Dynamic Programming Algorithms

In this paper we study quantum algorithms for NP-complete problems whose...

0 Andris Ambainis, et al. ∙

∙ 09/26/2017

All Classical Adversary Methods are Equivalent for Total Functions

We show that all known classical adversary lower bounds on randomized qu...

0 Andris Ambainis, et al. ∙

∙ 08/02/2017

Quadratically Tight Relations for Randomized Query Complexity

Let f:{0,1}^n →{0,1} be a Boolean function. The certificate complexity C...

0 Dmitry Gavinsky, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world