Quantum versus Randomized Communication Complexity, with Efficient Players

Quantum versus Randomized Communication Complexity, with Efficient Players

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


Duration: 20:35
191 views
3

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

Quantum versus Randomized Communication Complexity, with Efficient Players

Uma Girish (Princeton University)
Ran Raz (Princeton University)
Avishay Tal (UC Berkeley)



Other Videos By Simons Institute for the Theory of Computing


2021-01-15A New Connection Between Node and Edge Depth Robust Graphs
2021-01-15Training (Overparametrized) Neural Networks in Near-Linear Time
2021-01-15Communication memento: Memoryless communication complexity
2021-01-15Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
2021-01-15An O(n) time algorithm for finding Hamilton cycles with high probability
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-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