Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes
Offered By: IEEE via YouTube
Course Description
Overview
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.
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
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube