The Edge of Tractability: Unique Games vs Sum of Squares

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


Duration: 1:03:25
481 views
4

David Steurer, Cornell University
Semidefinite Optimization, Approximation and Applications
http://simons.berkeley.edu/talks/david-steurer-2014-09-23



Other Videos By Simons Institute for the Theory of Computing


2014-09-29Convex Optimization and Quantum Information
2014-09-29Faster SDP Hierarchy Solvers for Local Rounding Algorithms
2014-09-29Tensor Decompositions: Uniqueness and Smoothed Analysis
2014-09-29Convex Relaxations for Recovering Simultaneously Structured Objects
2014-09-29An SDP-based Algorithmic Cheeger Inequality for Vertex Expansion
2014-09-29Spectral Bounds and SDP Hierarchies for Geometric Packing Problems
2014-09-29A Polynomial Time Algorithm for Lossy Population Recovery
2014-09-29Learning Overcomplete Latent Variable Models through Tensor Power Method
2014-09-29Recovering Hidden Sparsity via Sum of Squares
2014-09-29Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
2014-09-29The Edge of Tractability: Unique Games vs Sum of Squares
2014-09-29Robust Sketching for Large-Scale Multi-Instance Conic Optimization
2014-09-19Wrap Session part 2
2014-09-19Wrap Session part 1
2014-09-19Wrap Session Discussion
2014-09-19Computing Multiplicities of Lie Group Representations
2014-09-19Combinatorics and Complexity of Kronecker Coefficients
2014-09-19Tutorial 3: Geometric Invariant Theory
2014-09-19Orbit Closures
2014-09-19Generalized Knuth Equivalence for Schur Positivity
2014-09-19A Survey of Recent Results on Depth Reduction and Lower Bounds for Arithmetic Circuits


Tags:
Simons Institute
UC Berkeley
computer science
theory of computing
Algorithmic Spectral Graph Theory
David Steurer