Zobrazeno 1 - 10
of 45
pro vyhledávání: '"Prūsis, Krišjānis"'
Autor:
Prūsis, Krišjānis, Vihrovs, Jevgēnijs
In this note we show examples of total Boolean functions that depend on $n$ variables and have spectral sensitivity $\Theta(\sqrt{\log n})$, which is asymptotically minimal.
Externí odkaz:
http://arxiv.org/abs/2412.16088
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 (Combinatorica 32, 2012) that uses $O(2.616^n)$ time and polynomial space
Externí odkaz:
http://arxiv.org/abs/2202.08186
Autor:
Kokainis, Martins, Prūsis, Krišjānis, Vihrovs, Jevgēnijs, Kashcheyevs, Vyacheslavs, Ambainis, Andris
Publikováno v:
J. Phys. A: Math. Theor. 55 495301 (2022)
We show that the discrete time quantum walk on the Boolean hypercube of dimension $n$ has a strong dispersion property: if the walk is started in one vertex, then the probability of the walker being at any particular vertex after $O(n)$ steps is of a
Externí odkaz:
http://arxiv.org/abs/2201.11735
Autor:
Ambainis, Andris, Balodis, Kaspars, Iraids, Jānis, Khadiev, Kamil, Kļevickis, Vladislavs, Prūsis, Krišjānis, Shen, Yixin, Smotrovs, Juris, Vihrovs, Jevgēnijs
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 depth of at most $k$. We call this the $Dyck_{k,n}$ problem. We prove a
Externí odkaz:
http://arxiv.org/abs/2007.03402
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 at most $k$. It has been known that, for any $k$, $\tilde{O}(\sqrt{n})
Externí odkaz:
http://arxiv.org/abs/1911.12638
We investigate the relation between the block sensitivity $\text{bs}(f)$ and fractional block sensitivity $\text{fbs}(f)$ complexity measures of Boolean functions. While it is known that $\text{fbs}(f) = O(\text{bs}(f)^2)$, the best known separation
Externí odkaz:
http://arxiv.org/abs/1810.02393
Autor:
Ambainis, Andris, Balodis, Kaspars, Iraids, Jānis, Kokainis, Martins, Prūsis, Krišjānis, Vihrovs, Jevgēnijs
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 in the hypercube problem that models many of these dynamic programming
Externí odkaz:
http://arxiv.org/abs/1807.05209
Autor:
Ambainis, Andris, Kokainis, Martins, Prūsis, Krišjānis, Vihrovs, Jevgēnijs, Zajakins, Aleksejs
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{fbs}(f)$. That includes the Kolmogorov complexity bound of Laplante an
Externí odkaz:
http://arxiv.org/abs/1709.08985
Autor:
Ibrahimov, Rishat, Khadiev, Kamil, Prusis, Krisjanis, Vihrovs, Jevgenijs, Yakaryilmaz, Abuzer
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. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be qua
Externí odkaz:
http://arxiv.org/abs/1703.07184
Autor:
Nakanishi, Masaki, Khadiev, Kamil, Prūsis, Krišjānis, Vihrovs, Jevgēnijs, Yakaryılmaz, Abuzer
Publikováno v:
EPTCS 252, 2017, pp. 205-218
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 language that can be recognized by exact realtime affine counter automat
Externí odkaz:
http://arxiv.org/abs/1703.04281