Faster SDP Hierarchy Solvers for Local Rounding Algorithms
summary
Claims a concrete speedup that removes the exponential-in-level bottleneck for solving SDP hierarchies, giving a provable runtime bound that scales polynomially rather than exponentially in the number of rounds. Uses matrix sketching and block coordinate / iterative projection ideas to produce low-rank rounding outputs that preserve the moments local rounding needs, includes theoretical approximation guarantees and small-scale experiments showing multi-fold wallclock improvement on standard combinatorial instances.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:25Recent Rounding Algorithms
- 3:38Motivation
- 8:08[Lau'03] An Example: k-clique
- 10:11Lower Bound on Running Time
- 12:00Our Result
- 21:28Main Idea
- 34:33Abstract Setting
- 35:24Rounding Algorithm Template
- 36:28Approximation Guarantees
- 37:25How To Fool The Rounding?
- 39:45Back to Certify.E
- 41:55P := separation oracle polytope
- 43:18Final Separation Oracle
- 44:00Conclusion
related talks
01h 01mLP/SDP Hierarchies and Sum of Squares Proofs 1
32mLocal Statistics, Semidefinite Programming, and Community Detection
01h 06mLP/SDP Hierarchies and Sum of Squares Proofs 4
59mLP/SDP Hierarchies and Sum of Squares Proofs 3
01h 04mLP/SDP Hierarchies and Sum of Squares Proofs 2
35mSmoothed Analysis of Low Rank Solutions to Semidefinite Programs via Burer Monteiro Factorization
01h 02mDuality 2
42mTight Semidefinite Programming Relaxations for Polynomial Optimization