Sunday, Aug 3: 2:00 PM - 3:50 PM
0347
Invited Paper Session
Music City Center
Room: CC-Davidson Ballroom A3
The speakers will cover recent advances in combinatorial optimization problems. The methods come from high-dimensional probability, often with inspiration from statistical physics. The session will address both static and algorithmic questions. To give a concrete example, several of the speakers have recent work on the perceptron model, from multiple viewpoints: one can ask about the geometry of the solution space (statics), or about the computational complexity of finding a solution given the disorder vectors as input (algorithmic). We expect that it will be fruitful to explore these multiple viewpoints in a combined session.
All the proposed speakers have confirmed to me that they would be willing to participate. However, one of them, Marcus Michelen, has informed me that he has a scheduling conflict, and will only be available to attend on either August 2 or 3, so ideally the session could be scheduled for one of those days. If not, then I will need to find a replacement speaker. Additionally, depending on scheduling and balance of topics, Brice Huang and Mark Sellke can potentially give one joint talk rather than two separate talks.
Applied
No
Main Sponsor
IMS
Presentations
How can we use randomness to generate dense sphere packings in high dimensions? "How many" sphere packings of a given density are there in high dimensions? We will discuss a probabilistic approach to this problem (joint with Campos, Jenssen and Sahasrabudhe) and connect these results to predictions from statistical physics by Parisi and Zamponi. We will end with a quick summary of yet another probabilistic approach to sphere packing in high dimensions (due to Klartag) and summarize some open problems about the place in randomness in the study of sphere packing.
We show that the shortest s-t path problem has the overlap-gap property in (i) sparse G(n,p) graphs and (ii) complete graphs with i.i.d. Exponential edge weights. Furthermore, we demonstrate that in sparse G(n,p) graphs, shortest path is solved by O(log n)-degree polynomial estimators, and a uniform approximate shortest path can be sampled in polynomial time. This constitutes the first example in which the overlap-gap property is not predictive of algorithmic intractability for a (non-algebraic) average-case optimization problem.
This is based on joint work with Tselil Schramm.
It is a folklore belief in the theory of spin glasses and disordered systems that out-of-equilibrium dynamics fail to find stable local optima (exhibiting local strong convexity) on physical time-scales. In the context of the Sherrington--Kirkpatrick spin glass, recent work has conjectured that this obstruction may be inherent to all efficient algorithms, despite the existence of exponentially many such optima throughout the landscape. We prove this search problem exhibits strong low degree hardness for polynomial algorithms of degree D≤o(N): any such algorithm has probability o(1) to output a stable local optimum. For spherical mean-field spin glasses with no external field, we also prove that the Langevin dynamics do not find stable local optima within dimension-free time. The first half of the talk will explain these results.
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.