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

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


Duration: 39:03
294 views
2

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



Other Videos By Simons Institute for the Theory of Computing


2017-11-27Welcome and Bird's Eye View of Michael's Work/Uniform Sampling and Inverse Maintenance
2017-11-22Finding Low-Rank Matrices: From Matrix Completion to Recent Trends
2017-11-17Algorithmic Decision Making and the Cost of Fairness
2017-11-17Biases Beyond Observation: Discovering Discrimination in Supervised Learning
2017-11-17Is Bias a Social or a Mathematical Concept?
2017-11-09Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture
2017-11-09Computing the Independence Polynomial in Shearer's Region for the LLL
2017-11-09Fast Spectral Algorithms from Sum-of-Squares Analyses
2017-11-09Nonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning
2017-11-09From Proofs to Algorithms for Machine Learning Problems
2017-11-08Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs
2017-11-08Independent Set Polytopes: Query vs. Communication Perspective
2017-11-08Counting and Optimization Using Stable Polynomials
2017-11-08Spectrahedra and Directional Derivatives of Determinants
2017-11-08Maximizing Sub-determinants and Connections to Permanents and Inequalities on Stable Polynomials
2017-11-08SOS and the Dreaded Bit-complexity
2017-11-07Matrix Completion and Sums of Squares
2017-11-07LP, SOCP, and Optimization-Free Approaches to Polynomial Optimization
2017-11-07From Weak to Strong LP Gaps for all CSPs
2017-11-07Spectral Aspects of Symmetric Matrix Signings
2017-11-07Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere


Tags:
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley
Hierarchies Extended Formulations and Matrix-Analytic Techniques
Raghu Meka