Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers

Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers

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


Duration: 34:22
111 views
3

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

Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers

Abhijit Mudigonda (None)
Ryan Williams (MIT)



Other Videos By Simons Institute for the Theory of Computing


2021-01-15Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
2021-01-15Sensitivity Analysis of the Maximum Matching Problem
2021-01-15On Distributed Differential Privacy and Counting Distinct Elements
2021-01-15A Generalized Matching Reconfiguration Problem
2021-01-15Agnostic learning with unknown utilities
2021-01-15Quantum versus Randomized Communication Complexity, with Efficient Players
2021-01-15No quantum speedup over gradient descent for non-smooth convex optimization
2021-01-15Sequential Defaulting in Financial Networks
2021-01-15Non-quasi-linear Agents in Quasi-linear Mechanisms
2021-01-15Online Search With a Hint
2021-01-15Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers
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-15On the Complexity of #CSP^d