Strong Low Degree Hardness of Strict Local Optima and other Random Optimization Problems, Part 2
Sunday, Aug 3: 3:20 PM - 3:45 PM
Invited Paper Session
Music City Center
The second half of the talk will discuss strong low degree hardness more broadly for other random optimization problems. The key is a general-purpose enhancement of the ensemble overlap gap property, which can be used to upgrade existing algorithmic barriers for spin glass optimization, maximum independent set, random k-SAT, and the Ising perceptron.
You have unsaved changes.