Lifting query complexity to time-space complexity for two-way finite automata
From MaRDI portal
Publication:6141040
DOI10.1016/j.jcss.2023.103494arXiv2311.18220OpenAlexW4389312187MaRDI QIDQ6141040
Yaqiao Li, Lvzhou Li, Minghua Pan, Shenggen Zheng, Jozef Gruska
Publication date: 22 January 2024
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2311.18220
quantum computingcommunication complexitytwo-way finite automataquery algorithmslifting theoremstime-space complexity
Cites Work
- A direct product theorem for two-party bounded-round public-coin communication complexity
- State succinctness of two-way finite automata with quantum and classical states
- One-way reversible and quantum finite automata with advice
- Quantum finite automata: advances on Bertoni's ideas
- An application of quantum finite automata to interactive proof systems
- Improved constructions of quantum automata
- Tradeoffs for language recognition on alternating machines
- A time-space tradeoff for sorting on non-oblivious machines
- Fooling a two way automaton or one pushdown store is better than one counter for two way machines
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Quantum automata and quantum grammars
- Time-space tradeoffs for branching programs
- Two-way finite automata with quantum and classical states.
- Complexity measures and decision tree complexity: a survey.
- On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
- Revisiting Deutsch-Jozsa algorithm
- On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
- Simulation theorems via pseudo-random properties
- Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
- On exact quantum query complexity
- On hybrid models of quantum finite automata
- Some formal tools for analyzing quantum automata.
- Superlinear Advantage for Exact Quantum Algorithms
- Forrelation
- From Quantum Query Complexity to State Complexity
- Generalizations of the distributed Deutsch–Jozsa promise problem
- New One Shot Quantum Protocols With Application to Communication Complexity
- One-Way Finite Automata with Quantum and Classical States
- On quantum and probabilistic communication
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
- Quantum time-space tradeoffs for sorting
- A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
- Separations in Query Complexity Based on Pointer Functions
- Communication Complexity
- UNDERSTANDING QUANTUM ALGORITHMS VIA QUERY COMPLEXITY
- Communication Complexity
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Query-to-Communication Lifting Using Low-Discrepancy Gadgets
- An optimal separation of randomized and Quantum query complexity
- Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Lifting query complexity to time-space complexity for two-way finite automata
