Wednesday, May 20, 2026 - 12:00pm
Event Calendar Category
Other LIDS Events
Speaker Name
Eren Kizildag
Affiliation
University of Illinois Urbana-Champaign
Building and Room number
32-D650
Building and Room Number
LIDS Lounge
"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.