6.S977 The Sum of Squares Method
Repeats every week every Tuesday and every Thursday until Tue Dec 10 2024 except Tue Oct 15 2024, Thu Nov 28 2024.
Thu, 09/05/2024 - 9:30am to 11:00amLocation:
3-442
Instructor:
Sam Hopkins
What is the relationship between mathematical proofs and efficient algorithms?
We will study this question through the lens of the sum of squares method, a powerful framework for algorithm design linking mathematical proofs, polynomials, and optimization, which generalizes linear programming and spectral methods. Along the way, we will describe and analyze state-of-the-art algorithms for foundational problems from combinatorial optimization, high-dimensional statistics, quantum information, cryptoanalysis, and beyond, and touch on questions from worst-case and average-case computational complexity.
Prerequisites: mathematical maturity, especially in linear algebra and probability.
We will study this question through the lens of the sum of squares method, a powerful framework for algorithm design linking mathematical proofs, polynomials, and optimization, which generalizes linear programming and spectral methods. Along the way, we will describe and analyze state-of-the-art algorithms for foundational problems from combinatorial optimization, high-dimensional statistics, quantum information, cryptoanalysis, and beyond, and touch on questions from worst-case and average-case computational complexity.
Prerequisites: mathematical maturity, especially in linear algebra and probability.