Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing

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


Duration: 23:45
112 views
2

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

Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines

Kunal Mittal (Princeton University)
Ran Raz (Princeton University)



Other Videos By Simons Institute for the Theory of Computing


2021-01-15Erasure-Resilient Sublinear-Time Graph Algorithms
2021-01-15How to Sell Information Optimally: an Algorithmic Study
2021-01-15Distributed load balancing: a new framework and improved guarantees
2021-01-15Learning and Strongly Truthful Multi-task Setting Peer Prediction: A Variational Approach
2021-01-15Batching and Optimal Multi-stage Bipartite Allocations
2021-01-15Buying Data Over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions
2021-01-15High-entropy dual functions and locally decodable codes
2021-01-15Randomness and Fairness in Two-Sided Matching with Limited Interviews
2021-01-15Counterexamples to the Low-Degree Conjecture
2021-01-15Majorizing Measures for the Optimizer
2021-01-15Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing
2021-01-15Shrinkage of Decision Lists and DNF Formulas
2021-01-15Quantitative Correlation Inequalities via Semigroup Interpolation
2021-01-15Differentially Oblivious Turing Machines
2021-01-15Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility
2021-01-15Online Paging with a Vanishing Regret
2021-01-15Towards local testability for quantum coding
2021-01-15Complete Problems for Multi-Pseudodeterministic Computations
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