Two-way and one-way quantum and classical automata with advice for online minimization problems
From MaRDI portal
Publication:2139057
Recommendations
Cites work
- scientific article; zbMATH DE number 3254906 (Why is no real title available?)
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- Branching Programs and Binary Decision Diagrams
- Classical and Quantum Computations with Restricted Memory
- Comparative complexity of quantum and classical OBDDs for total and partial functions
- Competitive Analysis of Aggregate Max in Windowed Streaming
- Competitive analysis of maintaining frequent items of a stream
- Design and analysis of randomized algorithms. Introduction to design paradigms.
- Exponential separations for one-way quantum communication complexity, with applications to cryptography
- Extension of the hierarchy for \(k\)-OBDDs of small width
- How Much Information about the Future Is Needed?
- Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test
- New size hierarchies for two way automata
- Nondeterministic unitary OBDDs
- On the Advice Complexity of Online Problems
- On the computational power of probabilistic and quantum branching program
- On the power of randomness versus advice in online computation
- Online Computation with Advice
- Online computation with advice
- Quantum branching programs and space-bounded nonuniform quantum complexity
- Quantum finite automata: a modern introduction
- Quantum online algorithms with respect to space and advice complexity
- Quantum online streaming algorithms with logarithmic memory
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- Superiority of exact quantum automata for promise problems
- The Frequent Items Problem in Online Streaming Under Various Performance Measures
- The string guessing problem as a method to prove lower bounds on the advice complexity
- Two-way finite automata with quantum and classical states.
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- Width hierarchy for \(k\)-OBDD of small width
Cited in
(5)- The fast algorithm for online \(k\)-server problem on trees
- Quantum algorithm for dynamic programming approach for DAGs and applications
- Mirrors and memory in quantum automata
- Time efficient implementation for online \(k\)-server problem on trees
- Quantum versus classical online streaming algorithms with logarithmic size of memory
This page was built for publication: Two-way and one-way quantum and classical automata with advice for online minimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2139057)
