Lifting query complexity to time-space complexity for two-way finite automata
From MaRDI portal
Publication:6141040
Recommendations
- Time-Space Complexity Advantages for Quantum Computing
- State succinctness of two-way finite automata with quantum and classical states
- The complexity of probabilistic versus quantum finite automata
- Two-way finite automata with quantum and classical states.
- From quantum query complexity to state complexity
Cites work
- A direct product theorem for two-party bounded-round public-coin communication complexity
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- A time-space tradeoff for sorting on non-oblivious machines
- A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
- An application of quantum finite automata to interactive proof systems
- An optimal separation of randomized and Quantum query complexity
- Communication Complexity
- Communication Complexity
- Complexity measures and decision tree complexity: a survey.
- Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
- Fooling a two way automaton or one pushdown store is better than one counter for two way machines
- Forrelation: a problem that optimally separates quantum from classical computing
- From quantum query complexity to state complexity
- Generalizations of the distributed Deutsch-Jozsa promise problem
- scientific article; zbMATH DE number 4026854 (Why is no real title available?)
- scientific article; zbMATH DE number 3765145 (Why is no real title available?)
- scientific article; zbMATH DE number 3456838 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 2040892 (Why is no real title available?)
- scientific article; zbMATH DE number 2050931 (Why is no real title available?)
- scientific article; zbMATH DE number 1775389 (Why is no real title available?)
- scientific article; zbMATH DE number 1361468 (Why is no real title available?)
- Improved constructions of quantum automata
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- New One Shot Quantum Protocols With Application to Communication Complexity
- On exact quantum query complexity
- On hybrid models of quantum finite automata
- On quantum and probabilistic communication: Las Vegas and one-way protocols
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- One-way finite automata with quantum and classical states
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Quantum automata and quantum grammars
- Quantum finite automata: advances on Bertoni's ideas
- Quantum time-space tradeoffs for sorting
- Query-to-communication lifting using low-discrepancy gadgets
- Revisiting Deutsch-Jozsa algorithm
- Simulation theorems via pseudo-random properties
- Some formal tools for analyzing quantum automata.
- State succinctness of two-way finite automata with quantum and classical states
- Succinctness of two-way probabilistic and quantum finite automata
- Superlinear advantage for exact quantum algorithms
- Time-space tradeoffs for branching programs
- Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
- Tradeoffs for language recognition on alternating machines
- Two-way finite automata with quantum and classical states.
- Understanding quantum algorithms via query complexity
This page was built for publication: Lifting query complexity to time-space complexity for two-way finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6141040)
