Lifting query complexity to time-space complexity for two-way finite automata (Q6141040): Difference between revisions

@@ Property / DOI @@
-.1016/j.jcss.2023.103494
@@ Property / DOI: 10.1016/j.jcss.2023.103494 / rank @@
-Normal rank
@@ Property / OpenAlex ID @@
+W4389312187
@@ Property / OpenAlex ID: W4389312187 / rank @@
+Normal rank
@@ Property / cites work @@
+Forrelation
@@ Property / cites work: Forrelation / rank @@
+Normal rank
@@ Property / cites work @@
+Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
+Normal rank
@@ Property / cites work @@
+Superlinear Advantage for Exact Quantum Algorithms
+Normal rank
@@ Property / cites work @@
+UNDERSTANDING QUANTUM ALGORITHMS VIA QUERY COMPLEXITY
+Normal rank
@@ Property / cites work @@
+Separations in Query Complexity Based on Pointer Functions
+Normal rank
@@ Property / cites work @@
+Improved constructions of quantum automata
@@ Property / cites work: Improved constructions of quantum automata / rank @@
+Normal rank
@@ Property / cites work @@
+Two-way finite automata with quantum and classical states.
+Normal rank
@@ Property / cites work @@
+New One Shot Quantum Protocols With Application to Communication Complexity
+Normal rank
@@ Property / cites work @@
+Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
+Normal rank
@@ Property / cites work @@
+A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
+Normal rank
@@ Property / cites work @@
+Time-space tradeoffs for branching programs
@@ Property / cites work: Time-space tradeoffs for branching programs / rank @@
+Normal rank
@@ Property / cites work @@
+Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
+Normal rank
@@ Property / cites work @@
+Q4452048
@@ Property / cites work: Q4452048 / rank @@
+Normal rank
@@ Property / cites work @@
+Some formal tools for analyzing quantum automata.
@@ Property / cites work: Some formal tools for analyzing quantum automata. / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum finite automata: advances on Bertoni's ideas
+Normal rank
@@ Property / cites work @@
+A time-space tradeoff for sorting on non-oblivious machines
+Normal rank
@@ Property / cites work @@
+Q4542521
@@ Property / cites work: Q4542521 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity measures and decision tree complexity: a survey.
+Normal rank
@@ Property / cites work @@
+Query-to-Communication Lifting Using Low-Discrepancy Gadgets
+Normal rank
@@ Property / cites work @@
+Simulation theorems via pseudo-random properties
@@ Property / cites work: Simulation theorems via pseudo-random properties / rank @@
+Normal rank
@@ Property / cites work @@
+Fooling a two way automaton or one pushdown store is better than one counter for two way machines
+Normal rank
@@ Property / cites work @@
+A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
+Normal rank
@@ Property / cites work @@
+Q3947125
@@ Property / cites work: Q3947125 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228473
@@ Property / cites work: Q4228473 / rank @@
+Normal rank
@@ Property / cites work @@
+Generalizations of the distributed Deutsch–Jozsa promise problem
+Normal rank
@@ Property / cites work @@
+Q3768423
@@ Property / cites work: Q3768423 / rank @@
+Normal rank
@@ Property / cites work @@
+Tradeoffs for language recognition on alternating machines
+Normal rank
@@ Property / cites work @@
+On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
+Normal rank
@@ Property / cites work @@
+Q4699286
@@ Property / cites work: Q4699286 / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
+Normal rank
@@ Property / cites work @@
+A direct product theorem for two-party bounded-round public-coin communication complexity
+Normal rank
@@ Property / cites work @@
+Q4453205
@@ Property / cites work: Q4453205 / rank @@
+Normal rank
@@ Property / cites work @@
+On quantum and probabilistic communication
@@ Property / cites work: On quantum and probabilistic communication / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum time-space tradeoffs for sorting
@@ Property / cites work: Quantum time-space tradeoffs for sorting / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
+Normal rank
@@ Property / cites work @@
+Q4043014
@@ Property / cites work: Q4043014 / rank @@
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On hybrid models of quantum finite automata
@@ Property / cites work: On hybrid models of quantum finite automata / rank @@
+Normal rank
@@ Property / cites work @@
+On exact quantum query complexity
@@ Property / cites work: On exact quantum query complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Quantum automata and quantum grammars
@@ Property / cites work: Quantum automata and quantum grammars / rank @@
+Normal rank
@@ Property / cites work @@
+An application of quantum finite automata to interactive proof systems
+Normal rank
@@ Property / cites work @@
+Revisiting Deutsch-Jozsa algorithm
@@ Property / cites work: Revisiting Deutsch-Jozsa algorithm / rank @@
+Normal rank
@@ Property / cites work @@
+Communication Complexity
@@ Property / cites work: Communication Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+An optimal separation of randomized and Quantum query complexity
+Normal rank
@@ Property / cites work @@
+Q5414546
@@ Property / cites work: Q5414546 / rank @@
+Normal rank
@@ Property / cites work @@
+One-way reversible and quantum finite automata with advice
+Normal rank
@@ Property / cites work @@
+From Quantum Query Complexity to State Complexity
@@ Property / cites work: From Quantum Query Complexity to State Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
+Normal rank
@@ Property / cites work @@
+State succinctness of two-way finite automata with quantum and classical states
+Normal rank
@@ Property / cites work @@
+One-Way Finite Automata with Quantum and Classical States
+Normal rank
@@ Property / DOI @@
+.1016/J.JCSS.2023.103494
@@ Property / DOI: 10.1016/J.JCSS.2023.103494 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:6141040