About this podcast

Dive into the mind of Richard Karp, a titan of theoretical computer science and Turing Award laureate. As a distinguished Berkeley professor, Karp revolutionized the field with his groundbreaking work on algorithms and complexity theory. Discover his pivotal contributions, including the Edmonds-Karp and Hopcroft-Karp algorithms, essential for network flow and graph matching. Explore the profound impact of his landmark paper, "Reducibility Among Combinatorial Problems," which identified 21 NP-complete problems and ignited global interest in NP-completeness and the P vs NP challenge. This discussion covers algorithmic complexity, P=NP, the stable marriage problem, randomized algorithms, machine learning, and open problems in theoretical computer science. Join us for an engaging exploration of the core ideas that shaped modern computing.