25 citations · 171 across the 48 of their papers we have counts for
4 papers · 1 filter
On the Complexity of Solving Subtraction Games
Kamil Khadiev, Dmitry Kravchenko
We study algorithms for solving Subtraction games, which sometimes are referred to as one-heap Nim games. We describe a quantum algorithm which is applicable to any game on DAG, an…
Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs
Kamil Khadiev, Liliya Safina
In this paper, we present a quantum algorithm for dynamic programming approach for problems on directed acyclic graphs (DAGs). The running time of the algorithm is $O(\sqrt{\hat{n}…
Quantum versus Classical Online Streaming Algorithms with Advice
Kamil Khadiev, Aliya Khadieva, Mansur Ziatdinov +4
We consider online algorithms with respect to the competitive ratio. Here, we investigate quantum and classical one-way automata with non-constant size of memory (streaming algorit…
New Size Hierarchies for Two Way Automata
Kamil Khadiev, Rishat Ibrahimov, Abuzer Yakary
We introduce a new type of nonuniform two--way automaton that can use a different transition function for each tape square. We also enhance this model by allowing to shuffle the gi…