An SDP-based Algorithmic Cheeger Inequality for Vertex Expansion

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


Duration: 54:39
341 views
2

Santosh Vempala, Georgia Institute of Technology
Semidefinite Optimization, Approximation and Applications
http://simons.berkeley.edu/talks/santosh-vempala-2014-09-24



Other Videos By Simons Institute for the Theory of Computing


2014-10-21Some Results and Questions as to the Complexity of the (Eigenvalue, Eigenvector) Problem
2014-10-21Real Algebraic Geometry in Computational Game Theory
2014-10-21On the Complexity of Solving Bivariate Systems
2014-10-21Sign Conditions for Injectivity of Generalized Polynomial Maps with Applications to Chemical ...
2014-10-21Descartes' Rule of Signs for Polynomial Systems Supported on Circuits
2014-10-21Solvability of Systems of Polynomial Equations over Finite Fields
2014-10-20Profile of Luca Trevisan, the Simons Institute's Incoming Senior Scientist
2014-10-07The Revolution in Graph Theoretic Optimization
2014-09-29Serialrank: Spectral Ranking using Seriation
2014-09-29Convex Optimization and Quantum Information
2014-09-29An SDP-based Algorithmic Cheeger Inequality for Vertex Expansion
2014-09-29Spectrahedra and their Shadows
2014-09-29Robust PCA via Non-convex Methods: Provable Bounds
2014-09-29Adventures in Linear Algebra++ and Unsupervised Learning
2014-09-29Noncommutative Polynomial Optimization under Dimension Constraints
2014-09-29Convergence of SDP Hierarchies Using Kernel Based Methods: Moment Matrices
2014-09-29The Edge of Tractability: Unique Games vs Sum of Squares
2014-09-29Positive Semidefinite Rank
2014-09-29Relative Entropy Relaxations for Signomial Optimization
2014-09-29Robust Sketching for Large-Scale Multi-Instance Conic Optimization
2014-09-19Wrap Session part 2


Tags:
Simons Institute
UC Berkeley
computer science
theory of computing
Algorithmic Spectral Graph Theory
Santosh Vempala