Computational Complexity in Theory and in Practice by Richard M. Karp

DISTINGUISHED LECTURES COMPUTATIONAL COMPLEXITY IN THEORY AND IN PRACTICE SPEAKER: Richard M. Karp (Professor Emeritus, Electrical Engineering and Computer Science, University of California, Berkeley) DATE: 18 October 2019, 15:30 to 16:45 VENUE: Chandrasekhar Auditorium, ICTS-TIFR, Bengaluru The quest for efficient algorithms is central both to theoretical computer science and to the practice of computing, but the metrics used in the two areas are different: theoreticians usually evaluate algorithms by their worst-case performance, whereas practitioners are more interested in empirical performance. This talk will contrast the two approaches through a series of examples. On the theory side, we will cover the complexity classes P and NP, NP-completeness, approximation algorithms and hardness of approximation. On the practical side, we will discuss satisfiability solvers, linear and integer programming, the traveling salesman problem, deep learning algorithms and game playing programs based on reinforcement learning.