Completed
What happens on random graphs?
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Local Minima, Stable Sets, and Sums of Squares
Automatically move to the next video in the Classroom when playback concludes
- 1 Intro
- 2 A bird's eye view of optimization
- 3 Step size too small
- 4 Forcing a smart initialization?
- 5 Finding a local minimum
- 6 Finding a local minimizer of a quadratic program
- 7 Stable sets in graphs
- 8 Proof outline
- 9 What about the unconstrained case?
- 10 Finding local minima of cubics Let's start with a simpler question. Can we efficiently find a critical point
- 11 Unexpected convexity
- 12 Local minima of cubics and SDP
- 13 All roads lead to sums of squares
- 14 A more complete story
- 15 Remainder of the talk
- 16 Nonnegativity vs. sum of squares
- 17 Nonnegative polynomials that are not SOS?
- 18 A new notion: SOS-perfect graphs
- 19 Example
- 20 An immediate implication
- 21 What happens on random graphs?
- 22 A challenge for the SOS/SDP community is
- 23 Feel the need for more SOS?
