Sum-Of-Squares To Approximate Knapsack

Pravesh K. Kothari, Sherry Sarkar

These notes give a self-contained exposition of Karlin, Mathieu and Nguyen's tight estimate of the integrality gap of the sum-of-squares semidefinite program for solving the knapsa…