Abstract
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 online algorithms. For a specially constructed online minimization problem, we provide a quantum log-bounded automaton that is more effective (has less competitive ratio) than classical automata, even with advice, in the case of the logarithmic size of memory. We construct an online version of the well-known Disjointness problem as a problem. It was investigated by many researchers from a communication complexity and query complexity point of view.
| Original language | English |
|---|---|
| Article number | 143 |
| Journal | Mathematics |
| Volume | 10 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1 Jan 2022 |
OECD Field of Science
- 1.1 Mathematics
Keywords
- Automata
- Online algorithms
- Online minimization problems
- Quantum computation
- Streaming algorithms
Fingerprint
Dive into the research topics of 'Quantum and Classical Log-Bounded Automata for the Online Disjointness Problem'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver