Lex Fridman
@lexfridman·4.9M subscribers·864 videos
What Is Algorithmic Complexity? | Richard Karp and Lex Fridman
Posted
July 31, 2020
Views
1,056
Likes
37
Comments
1
Engagement
3.60%
July 31, 2020
1,056
37
1
3.60%
Every word spoken in this episode is indexed. Type any phrase to jump straight to the moment it was said.
Type any word or phrase that may have been spoken. Click a result to seek the player to that exact moment.
Try a name, a topic, or a quoted line
10:14Now PlayingFull episode with Richard Karp (Jul 2020)
Clips channel (Lex Clips)
Main channel (Lex Fridman)
(more links below)
Podcast full episodes playlist:
Podcasts clips playlist:
Podcast website:
Podcast on Apple Podcasts (iTunes):
Podcast on Spotify:
Podcast RSS:
Richard Karp is a professor at Berkeley and one of the most important figures in the history of theoretical computer science. In 1985, he received the Turing Award for his research in the theory of algorithms, including the development of the Edmonds–Karp algorithm for solving the maximum flow problem on networks, Hopcroft–Karp algorithm for finding maximum cardinality matchings in bipartite graphs, and his landmark paper in complexity theory called "Reducibility Among Combinatorial Problems", in which he proved 21 problems to be NP-complete. This paper was probably the most important catalyst in the explosion of interest in the study of NP-completeness and the P vs NP problem.
Subscribe to this YouTube channel or connect on:
Support on Patreon
Sentinel Indexing in Progress
Metadata and chapters are available. Claim extraction for this episode is pending.
All video content is delivered via YouTube embedded players in accordance with the YouTube Terms of Service. Sentinel provides research tools that promote discovery and accountability across political media.
