Classical and quantum computations with restricted memory
Abstract Automata and branching programs are known models of computation with restricted
memory. These models of computation were in focus of a large number of researchers …
memory. These models of computation were in focus of a large number of researchers …
Quantum and classical log-bounded automata for the online disjointness problem
K Khadiev, A Khadieva - Mathematics, 2022 - mdpi.com
We consider online algorithms with respect to the competitive ratio. In this paper, we explore
one-way automata as a model for online algorithms. We focus on quantum and classical …
one-way automata as a model for online algorithms. We focus on quantum and classical …
Quantum online algorithms with respect to space and advice complexity
K Khadiev, A Khadieva, I Mannapov - Lobachevskii Journal of …, 2018 - Springer
Online computation is a well-known area of computer science. We introduce quantum online
algorithms and investigate them with respect to a competitive ratio in two points of view …
algorithms and investigate them with respect to a competitive ratio in two points of view …
Quantum online streaming algorithms with logarithmic memory
K Khadiev, A Khadieva - International Journal of Theoretical Physics, 2021 - Springer
We consider quantum and classical (deterministic or randomize) streaming online
algorithms with respect to competitive ratio. We show that there is a problem that can be …
algorithms with respect to competitive ratio. We show that there is a problem that can be …
Two-way and one-way quantum and classical automata with advice for online minimization problems
K Khadiev, A Khadieva, M Ziatdinov, I Mannapov… - Theoretical Computer …, 2022 - Elsevier
We consider online algorithms. Typically, the model is investigated with respect to the
competitive ratio. In this paper, we explore two-way automata and one-way automata as …
competitive ratio. In this paper, we explore two-way automata and one-way automata as …
Two-way quantum and classical machines with small memory for online minimization problems
K Khadiev, A Khadieva - … on Micro-and Nano-Electronics 2018, 2019 - spiedigitallibrary.org
We consider online algorithms. Typically the model is investigated with respect to
competitive ratio. In this paper, we explore algorithms with small memory. We investigate two …
competitive ratio. In this paper, we explore algorithms with small memory. We investigate two …
The frequent items problem in online streaming under various performance measures
This is a contribution to the ongoing study of properties of performance measures for online
algorithms. It has long been known that competitive analysis suffers from draw-backs in …
algorithms. It has long been known that competitive analysis suffers from draw-backs in …
Two-way quantum and classical automata with advice for online minimization problems
K Khadiev, A Khadieva - … FM 2019 International Workshops: Porto, Portugal …, 2020 - Springer
We consider online algorithms. Typically the model is investigated with respect to
competitive ratio. In this paper, we explore two-way automata as a model for online …
competitive ratio. In this paper, we explore two-way automata as a model for online …
Quantum versus classical online streaming algorithms with logarithmic size of memory
K Khadiev, A Khadieva, D Kravchenko… - Lobachevskii Journal of …, 2023 - Springer
We consider online algorithms with respect to the competitive ratio. Here, we investigate
quantum and classical one-way automata with a non-constant size of memory (streaming …
quantum and classical one-way automata with a non-constant size of memory (streaming …
Online bounded analysis
Though competitive analysis is often a very good tool for the analysis of online algorithms,
sometimes it does not give any insight and sometimes it gives counter-intuitive results. Much …
sometimes it does not give any insight and sometimes it gives counter-intuitive results. Much …