Talks
Spring 2021

Where The Really Hard Problems Really Are?

Thursday, Apr. 22, 2021 8:30 am9:30 am

Add to Calendar

Speaker: 

Lenka Zdeborova (EPFL)

Location: 

Zoom

While the K-SAT problem is the cornerstone of the worst-case computational complexity theory, the random K-SAT problem serves for decades as a prototype of probability distribution to explore the average computational hardness of natural distributions of instances. While a complete and formal theory is not yet in sight, progress has been made in various directions. In this talk, I will review what we know about the algorithmic hardness of random K-SAT and more generally random constraint satisfaction problems. Several concrete conjectures about where the really hard problems really are will be discussed. I will also present close connections to the hardness of problems in statistical inference and learning.