09/26—strengths and limitations of sos for max cut and expansion

reading: max cut algorithm, expansion algorithm, lower bounds

10/03—degree-4 sos approximation for expansion

reading: ARV algorithm (pdf-version)

10/10—no lecture due to FOCS conference

10/17—exponential lower bounds for sum-of-squares

reading: higher-degree integrality gaps: from computational hardness to limitations of sum-of-squares (pdf-version)

10/24—calibration and planted clique lower bounds for sum-of-squares

reading: integrality gap for planted clique (pdf-version) sum-of-squares for general domains (pdf-version)

10/31—no lecture due to Fall break

11/07—polynomials over the sphere: planted sparse vectors

11/14—polynomials over the sphere: tensor decomposition

11/21—optimality of SOS and spectralhedral lifts of polytopes

11/28—quantum entanglement and the log rank conjecture