Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum

Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=K-EG81SGAw8


Category:
Vlog
Duration: 29:05
72 views
1

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
http://itcs-conf.org/

Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines

Zachary Remscrim (The University of Chicago)



Other Videos By Simons Institute for the Theory of Computing


2021-01-15Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers
2021-01-15Robust Quantum Entanglement at (nearly) Room Temperature
2021-01-15Pseudobinomiality of the Sticky Random Walk
2021-01-15Black-Box Uselessness: Composing Separations in Cryptography
2021-01-15Tiered Random Matching Markets: Rank is Proportional to Popularity
2021-01-15Relaxing Common Belief for Social Networks
2021-01-15Total Functions in the Polynomial Hierarchy
2021-01-15Ordered Graph Limits and Their Applications
2021-01-15Shrinkage under random projections, and cubic formula lower bounds in AC^0
2021-01-15Interactive Proofs for Verifying Machine Learning
2021-01-15Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum
2021-01-15Sampling Arborescences in Parallel
2021-01-15Explicit SoS lower bounds from high-dimensional expanders
2021-01-15Two combinatorial MA-complete problems
2021-01-15Delegated Stochastic Probing
2021-01-15Is the space complexity of planted clique recovery the same as that of detection?
2021-01-15Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate
2021-01-15Bounds on the QAC0 Complexity of Approximating Parity
2021-01-15Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
2021-01-15On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism
2021-01-15On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions