Low-Degree Hardness of Random Optimization Problems
Offered By: IEEE via YouTube
Course Description
Overview
Explore the intricacies of random optimization problems in this 19-minute IEEE conference talk. Delve into topics such as max independent set, planted problems, and spherical spin glass results. Gain insights from experts David Gamarnik, Aukosh Jagannath, and Alexander S. Wein as they discuss ensemble OGP and provide valuable comments on the subject. Discover what's missing in current approaches and expand your understanding of low-degree hardness in random optimization.
Syllabus
Random Optimization Problems
Max Independent Set
What's Missing?
Planted Problems (Continued)
Spherical Spin Glass: Results
Ensemble OGP
Comments
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