Explore a 22-minute IEEE conference talk delving into sum-of-squares lower bounds for the Sherrington-Kirkpatrick optimization problem. Learn about the certification problem, sum-of-squares hierarchy, and key concepts like kinetic tense problem, correction, graph matrices, spiders, and their relation to null space. Gain insights from experts Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran as they discuss current knowledge, proof techniques, and open problems in this complex mathematical field.
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes
Overview
Syllabus
Introduction
SherringtonKirkpatrick
Optimization Problem
Certification Problem
SumofSquares Hierarchy
What is known
Proof
Kinetic Tense Problem
Correction
Graph matrices
Spiders
Spiders and Null Space
Open Problems
Taught by
IEEE FOCS: Foundations of Computer Science
