Sum of Squares Lower Bounds for Refuting Any CSP

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


Duration: 30:31
1,067 views
12

Ryan O'Donnell, Carnegie Mellon University
https://simons.berkeley.edu/talks/ryan-odonnell-2017-4-10
Structure vs. Randomness



Other Videos By Simons Institute for the Theory of Computing


2017-04-12Random High-Dimensional Combinatorial Objects
2017-04-12Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs
2017-04-12Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs
2017-04-11On Structural Properties of Low Threshold Rank Graphs
2017-04-11Additive Structure of Sets of Fourier Coefficients
2017-04-11Vinogradov's Three Primes Theorem with Primes from Special Sets
2017-04-11The Entropy Decrement Method and the Erdos Discrepancy Problem
2017-04-10Sparse Dense Dichotomy and Liquid Graphs
2017-04-10Trading Information Complexity for Error
2017-04-10Large Deviations for Arithmetic Progressions
2017-04-10Sum of Squares Lower Bounds for Refuting Any CSP
2017-04-10Algorithmic Dense Model Theorems and Weak Regularity
2017-04-04In Pursuit of Structure: Why a Little Randomness (Almost) Always Helps
2017-03-31Spotlght Talk: Performance Guarantees for Transferring Representations
2017-03-31Word Representation Learning without unk Assumptions
2017-03-31Resilient Representation and Provable Generalization
2017-03-31Learning Representations for Active Vision
2017-03-31Formation and Association of Symbolic Memories in the Brain
2017-03-31Learning Paraphrastic Representations of Natural Language Sentences
2017-03-30Provably Learning of Noisy-or Networks
2017-03-30Unsupervised Representation Learning


Tags:
Structure vs. Randomness
Ryan O'Donnell
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley