Yikai Wu will present his General Exam "Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set" on Wednesday, February 12, 2025 at 1:30 PM in CS 401 and via zoom. Zoom Link: https://princeton.zoom.us/j/97198300462 Committee Members: Sanjeev Arora (advisor), Elad Hazan, Pravesh Kothari Abstract: AI methods, especially generative models and reinforcement learning, have recently been applied to combinatorial optimization (CO) problems, especially NP-hard ones. This paper compares such GPU-based methods with classical CPU-based methods on Maximum Independent Set (MIS). Experiments on standard graph families show that AI-based algorithms fail to outperform and, in many cases, to even match the solution quality of classical solvers. The GPU-based methods often perform similarly to the simplest classical heuristic, degree-based greedy. Even when allowing ML-based methods to improve their solutions with post-processing techniques like local search, their performance remains inferior to that of CPU-based solvers. We develop a new mode of analysis to reveal that step-by-step AI methods, e.g. LTFT (which is based on GFlowNets), end up reasoning similarly to classical degree-based greedy approaches. We also find that CPU-based algorithms, notably Kamis, have strong performance on sparse random graphs, which appears to surpass a conjectured upper bound for polynomial algorithms. Reading List: https://docs.google.com/document/d/10wj4bZsLdrMIU402he0aC6HkxVSE_v9ujmnVgzzu... Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.