Optimization problems with random objective functions are central in computer science, probability, and modern data science. Despite their ubiquity, finding efficient algorithms for solving these problems remains a major challenge. Interestingly, many random optimization problems share a common feature, dubbed as a statistical-computational gap: while the optimal value can be pinpointed non-constructively (through, e.g., probabilistic/information-theoretic tools), all known polynomial-time algorithms find strictly sub-optimal solutions. That is, an optimal solution can only be found through brute force search which is computationally expensive.
In this talk, I will discuss an emerging theoretical framework for understanding the fundamental computational limits of random optimization problems, based on the Overlap Gap Property (OGP). This is an intricate geometrical property that achieves sharp algorithmic lower bounds against the best known polynomial-time algorithms for a wide range of random optimization problems. I will focus on two models to demonstrate the power of the OGP framework: (a) the symmetric binary perceptron, a random constraint satisfaction problem and a simple neural network classifying/storing random patterns, widely studied in computer science, probability, and statistics communities, and (b) the random number partitioning problem as well as its planted counterpart, a classical worst-case NP-hard problem whose average-case variant is closely related to the design of randomized controlled trials. In addition to yielding sharp algorithmic lower bounds, our techniques also give rise to new toolkits for the study of statistical-computational tradeoffs in other models, including the online setting.
Bio. Eren C. Kizildag is a Distinguished Postdoctoral Fellow at Columbia University, Department of Statistics. He received his PhD in Electrical Engineering and Computer Science from MIT in 2022, supervised by David Gamarnik. His research interests are at the intersection of computer science with probability, statistics, and data science. He is particularly interested in understanding statistical-computational tradeoffs in random computational problems and large-scale random models, as well as in mathematical foundations of machine learning and data science.

Date

Location

CII 3206

**Speaker:**Eren Kizildag from Columbia University