Showing 2018Show all
2 papers · 1 filter
quant-ph2018
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…
cs.DS2018
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…