Approximately 50 Years of Inapproximability

Madhu Sudan
Harvard University

In this talk celebrating the work of Mihalis Yannakais, we will briefly survey the roughly fifty years of progress in understanding the limits of computationally efficient solutions to combinatorial optimization problems, after the seminal work of Papadimitriou and Yannakakis, introducing the complexity class MAX SNP.