Approximating Sparse Semidefinite Programs

ACO Student Seminar
Friday, October 1, 2021 - 1:00pm for 1 hour (actually 50 minutes)
Skiles 314
Kevin Shu – Georgia Tech Math – kshu8@gatech.edu
Abhishek Dhawan

Please Note: Stream online at

Semidefinite programming is a useful type of convex optimization, which has applications in both graph theory and industrial engineering. Many semidefinite programs exhibit a kind of structured sparsity, which we can hope to exploit to reduce the memory requirements of solving such semidefinite programs. We will discuss an interesting relaxation of such sparse semidefinite programs, and a measurement of how well this relaxation approximates a true semidefinite program. We'll also discuss how these approximations relate to graph theory and the theory of sum-of-squares and nonnegative polynomials. This talk will not assume any background on semidefinite programming.