Playlist: 24 videos

Hierarchies, Extended Formulations and Matrix-Analytic Techniques

An important development in the area of convex relaxations has been the introduction of systematic ways of strengthening them by lift-and-project techniques. This leads to several hierarchies of LP/SDP relaxations: Lovasz-Schrijver, Sherali-Adams and...

0:31:52

From Weak to Strong LP Gaps for all CSPs

Madhur Tulsiani, Toyota Technological Institute at Chicago
https://simons.berkeley.edu/talks/madhur-tulsiani-11-9-17
Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Visit talk page
0:31:55

LP, SOCP, and Optimization-Free Approaches to Polynomial Optimization

Amir Ali Ahmadi, Princeton University
https://simons.berkeley.edu/talks/amir-ali-ahmadi-11-7-17
Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Visit talk page
0:28:53

Matrix Completion and Sums of Squares

Greg Blekherman, Georgia Institute of Technology
https://simons.berkeley.edu/talks/greg-blekherman-11-7-17
Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Visit talk page
0:33:21

SOS and the Dreaded Bit-complexity

Ryan O'Donnell, Carnegie Mellon University
https://simons.berkeley.edu/talks/ryan-o-donnell-11-7-17
Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Visit talk page
0:29:13

Maximizing Sub-determinants and Connections to Permanents and Inequalities on Stable Polynomials

Mohit Singh, Georgia Institute of Technology
https://simons.berkeley.edu/talks/mohit-singh-11-8-17
Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Visit talk page
0:32:20

Spectrahedra and Directional Derivatives of Determinants

James Saunderson, Monash University
https://simons.berkeley.edu/talks/james-saunderson-11-8-17
Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Visit talk page
1:6:43

Counting and Optimization Using Stable Polynomials

Nima Anari, Stanford University
https://simons.berkeley.edu/talks/nima-anari-11-8-17
Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Visit talk page
0:58:2

Independent Set Polytopes: Query vs. Communication Perspective

Mika Göös, University of Toronto
https://simons.berkeley.edu/talks/mika-goos-11-8-17
Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Visit talk page
0:39:3

Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs

Raghu Meka, UCLA
https://simons.berkeley.edu/talks/raghu-meka-11-8-17
Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Visit talk page
1:4:6

From Proofs to Algorithms for Machine Learning Problems

David Steurer, Cornell University
https://simons.berkeley.edu/talks/david-steurer-11-9-17
Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Visit talk page