| Title | : | Computational Complexity in Theory and in Practice |
| Speaker | : | Prof. Richard Karp (UC Berkeley) |
| Details | : | Tue, 15 Oct, 2019 4:00 PM @ ICSR Auditorium |
| 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 learning. Bio: Prof. Richard Karp is a computational theorist at the University of California, Berkeley where he is currently a Professor Emeritus. Prof. Karp has made many important discoveries in computer science, combinatorial algorithms, and operations research. He is most notable for his research in the theory of algorithms, for which he received the Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008. His major current research interests include bioinformatics. Prof. Karp attended Boston Latin School and Harvard University, receiving the Ph.D. in 1959. From 1959 to 1968 he was a member of the Mathematical Sciences Department at IBM Research. From 1968 to 1994 and from 1999 to the present he has been a professor at UC Berkeley, where he held the Class of 1939 Chair. From 1988 to 1995 and 1999 to the present he has been a Research Scientist at the International Computer Science Institute in Berkeley. He has served on other important academic positions including the founding Director of the Simons Institute for the Theory of Computing (2012-2017). The unifying theme in Prof. Karp's work has been the study of combinatorial algorithms. His 1972 paper, "Reducibility Among Combinatorial Problems," showed that many of the most commonly studied combinatorial problems are NP-complete, and hence likely to be intractable. Much of his work has concerned parallel algorithms, the probabilistic analysis of combinatorial optimization algorithms and the construction of randomized algorithms for combinatorial problems. His current research activities center around algorithmic methods in genomics and computer networking. He has supervised thirty-six PhD dissertations. His honors and awards also include (in addition to the ones mentioned above) : Fulkerson Prize, U.S. National Medal of Science, Harvey Prize (Technion), Centennial Medal (Harvard), Lanchester Prize, Von Neumann Theory Prize, Von Neumann Lectureship, Distinguished Teaching Award (Berkeley), Faculty Research Lecturer (Berkeley), Miller Research Professor (Berkeley), Babbage Prize and eight honorary degrees. He is a member of the U.S. National Academies of Sciences and Engineering, the American Philosophical Society and the French Academy of Sciences, and a Fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science, the Association for Computing Machinery and the Institute for Operations Research and Management Science. |
