Mihalis Yannakakis, Columbia University

Abstract

David Johnson made many fundamental contributions to computer science, including in the theory of NP-completeness, approximation algorithms, and the analysis of heuristics for hard optimization problems. In this talk I will discuss some of his pioneering work and its impact on our field, and reflect on our friendship through many years together at Bell Labs and afterwards.

[Video]