Reduction From Non-Unique Games to Boolean Unique Games

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


Duration: 1:02:00
282 views
7

Dana Moshkovitz (University of Texas, Austin)
https://simons.berkeley.edu/talks/reduction-non-unique-games-boolean-unique-games
Learning and Testing in High Dimensions



Other Videos By Simons Institute for the Theory of Computing


2020-12-17Learning Deep ReLU Networks is Fixed-Parameter Tractable
2020-12-17The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks in High Dimension
2020-12-16Analyzing Optimization and Generalization in Deep Learning via Dynamics of Gradient Descent
2020-12-16SGD Learns One-Layer Networks in WGANs
2020-12-16Recent Progress in Algorithmic Robust Statistics via the Sum-of-Squares Method
2020-12-16Phase Transitions for Detecting Latent Geometry in Random Graphs
2020-12-16Low-Degree Hardness of Random Optimization Problems
2020-12-15Counting and Sampling Subgraphs in Sublinear Time
2020-12-15Learning and Testing for Gradient Descent
2020-12-15Learning Ising Models from One, Ten or a Thousand Samples
2020-12-15Reduction From Non-Unique Games to Boolean Unique Games
2020-12-15Testing Noisy Linear Functions for Sparsity
2020-12-14VC Dimension and Distribution-Free Sample-Based Testing
2020-12-14Testing Monotonicity of Distributions Over High-Dimensional Posets
2020-12-12Rump Session
2020-12-12Circularity Based IO, Part 3
2020-12-12Circularity Based IO, Part 2
2020-12-11Circularity Based IO, Part 1
2020-12-11iO via Functional Encryption: Techniques and Challenges from LWE
2020-12-11Panel Discussion: Computational Assumptions
2020-12-11On the Assumptions Used for Obfuscation


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Dana Moshkovitz
Learning and Testing in High Dimensions