Kannan Krishnamurty's video: I AR CSE DEPT IIT MADRAS PRESENT LECTURE BY PROF RICHARD M KARP LECTURE

Richard M Karp Chair Launch and Lecture Computational Complexity in Theory and in Practice Prof. Richard Karp Professor Emeritus Computational theoristUniversity of California, Berkeley Bio: Prof. Karp is a computational theorist at the University of California, Berkeley where he is currently a Professor Emeritus. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008. He has served on important academic positions including the founding Director of the Simons Institute for the Theory of Computing (2012-2017). Prof. Karp has made many important discoveries in computer science, combinatorial algorithms, and operations research. His major current research interests include bioinformatics. Abstract: 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