Approximate Constraint Satisfaction Requires Large LP Relaxations

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


Duration: 47:22
737 views
11

James R. Lee, University of Washington
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/james-lee-2013-08-28



Other Videos By Simons Institute for the Theory of Computing


2013-09-04Association Schemes, Non-Commutative Polynomials and Lasserre Lower Bounds for Planted Clique
2013-09-04Agnostic Learning Over Permutation Invariant Distributions
2013-09-04Local Combinatorics, Or: What To Do With All Those Gigantic Graphs?
2013-09-04Locally Testable Codes and Cayley Graphs
2013-09-04On the Structure of Boolean Functions With Small Spectral Norm
2013-09-04Testing for Affine Invariant Properties of Algebraic Functions
2013-09-04Approximating Boolean Functions With Small-Depth Circuits
2013-09-04Deterministic Counting of Satisfying Assignments for Juntas of Degree-2 PTFs
2013-09-04Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions
2013-09-04Moment-Matching Polynomials
2013-09-04Approximate Constraint Satisfaction Requires Large LP Relaxations
2013-09-04The Analysis of Partially Symmetric Functions
2013-09-04Majority is Stablest: Discrete and SOS
2013-09-04Robust Gaussian Noise Stability
2013-09-04Beyond Locality-Sensitive Hashing
2013-09-04A Characterization of Strong Approximation Resistance
2013-09-04The Complexity of Somewhat Approximation Resistant Predicates
2013-09-04Approximation Algorithms For Projection Games
2013-09-04Hardness of Maximum Independent Set in Structured Hypergraphs
2013-09-04An Analytic Approach to Parallel Repetition
2013-09-04Approximation Resistance from Pairwise Independent Subgroups


Tags:
Simons Institute
Real Analysis
UC Berkeley
computer science
theory of computing
James R. Lee
James Lee