Understanding Computational Complexity: Theory & Practical Insights by Richard M. Karp 🧠
Explore the fundamentals of computational complexity with renowned expert Richard M. Karp. Discover how theory translates into real-world applications in this engaging lecture.
International Centre for Theoretical Sciences
2.0K views • Oct 18, 2019
About this video
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.
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.
Video Information
Views
2.0K
Likes
55
Duration
01:10:44
Published
Oct 18, 2019
User Reviews
4.5
(1)