LIDS Tea Talk: Eren Kizildag

"Optimal Hardness of Online Algorithms for Large Independent Sets"

I will discuss the large independent set problem in dense Erdős–Rényi random graphs. I will present a sharp computational threshold for online algorithms, a broad class that includes greedy algorithms as a special case. At a technical level, our approach introduces a novel variant of the Overlap Gap Property which combines both a carefully chosen stopping time and interpolation paths that evolve temporally as the algorithm progresses.

Based on joint work with David Gamarnik (MIT) and Lutz Warnke (UCSD): https://arxiv.org/pdf/2504.11450

‍

Eren Kizildag is an Assistant Professor in the Department of Statistics at the University of Illinois Urbana-Champaign, where he is also affiliated with the Department of Electrical and Computer Engineering. He received his PhD in Electrical Engineering and Computer Science from MIT and subsequently worked as a Distinguished Postdoctoral Fellow at Columbia University, Department of Statistics.

His research lies at the intersection of probability, high-dimensional statistics, and computer science. His current interests include algorithmic barriers in high-dimensional inference and random combinatorial structures, spin glass methods in statistics and optimization, and mathematics of data science. His distinctions include a Best Paper Award at Algorithmic Learning Theory (ALT) in 2026 and a Summa Cum Laude award at ISMRM in 2016.