Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111
Skills:
Algorithm Basics85%
Richard Karp is a professor at Berkeley and one of the key 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.
Support this podcast by signing up with these sponsors:
- Eight Sleep: https://eightsleep.com/lex
- Cash App - use code "LexPodcast" and download:
- Cash App (App Store): https://apple.co/2sPrUHe
- Cash App (Google Play): https://bit.ly/2MlvP5w
EPISODE LINKS:
Richard's wikipedia: https://en.wikipedia.org/wiki/Richard_M._Karp
PODCAST INFO:
Podcast website:
https://lexfridman.com/podcast
Apple Podcasts:
https://apple.co/2lwqZIr
Spotify:
https://spoti.fi/2nEwCF8
RSS:
https://lexfridman.com/feed/podcast/
Full episodes playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOdP_8GztsuKi9nrraNbKKp4
Clips playlist:
https://www.youtube.com/playlist?list=PLrAXtmErZgOeciFP3CBCIEElOJeitOr41
OUTLINE:
0:00 - Introduction
3:50 - Geometry
9:46 - Visualizing an algorithm
13:00 - A beautiful algorithm
18:06 - Don Knuth and geeks
22:06 - Early days of computers
25:53 - Turing Test
30:05 - Consciousness
33:22 - Combinatorial algorithms
37:42 - Edmonds-Karp algorithm
40:22 - Algorithmic complexity
50:25 - P=NP
54:25 - NP-Complete problems
1:10:29 - Proving P=NP
1:12:57 - Stable marriage problem
1:20:32 - Randomized algorithms
1:33:23 - Can a hard problem be easy in practice?
1:43:57 - Open problems in theoretical computer science
1:46:21 - A strange idea in complexity theory
1:50:49 - Machine learning
1:56:26 - Bioi
Watch on YouTube ↗
(saves to browser)
Sign in to unlock AI tutor explanation · ⚡30
Playlist
Uploads from Lex Fridman · Lex Fridman · 0 of 60
← Previous
Next →
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
Ido Portal: Movement
Lex Fridman
Ryan Hall: Moral Victory
Lex Fridman
Jimmy Pedro: Judo | Take It Uneasy Podcast
Lex Fridman
Foundations of Deep Learning (Hugo Larochelle, Twitter)
Lex Fridman
TensorFlow Tutorial (Sherry Moore, Google Brain)
Lex Fridman
Nuts and Bolts of Applying Deep Learning (Andrew Ng)
Lex Fridman
Sequence to Sequence Deep Learning (Quoc Le, Google)
Lex Fridman
Torch Tutorial (Alex Wiltschko, Twitter)
Lex Fridman
Theano Tutorial (Pascal Lamblin, MILA)
Lex Fridman
Deep Reinforcement Learning (John Schulman, OpenAI)
Lex Fridman
Deep Learning for Speech Recognition (Adam Coates, Baidu)
Lex Fridman
Deep Learning for Natural Language Processing (Richard Socher, Salesforce)
Lex Fridman
Foundations of Unsupervised Deep Learning (Ruslan Salakhutdinov, CMU)
Lex Fridman
Deep Learning for Computer Vision (Andrej Karpathy, OpenAI)
Lex Fridman
Foundations and Challenges of Deep Learning (Yoshua Bengio)
Lex Fridman
MIT 6.S094: Introduction to Deep Learning and Self-Driving Cars
Lex Fridman
MIT 6.S094: Deep Reinforcement Learning for Motion Planning
Lex Fridman
MIT 6.S094: Convolutional Neural Networks for End-to-End Learning of the Driving Task
Lex Fridman
MIT 6.S094: Recurrent Neural Networks for Steering Through Time
Lex Fridman
MIT 6.S094: Deep Learning for Human-Centered Semi-Autonomous Vehicles
Lex Fridman
Chris Gerdes (Stanford) on Technology, Policy and Vehicle Safety - MIT Self-Driving Cars
Lex Fridman
Sertac Karaman (MIT) on Motion Planning in a Complex World - MIT Self-Driving Cars
Lex Fridman
MIT Sloan: Intro to Machine Learning (in 360/VR)
Lex Fridman
MIT 6.S094: Deep Learning
Lex Fridman
MIT Self-Driving Cars (2018)
Lex Fridman
MIT 6.S094: Deep Reinforcement Learning
Lex Fridman
MIT 6.S094: Computer Vision
Lex Fridman
MIT 6.S094: Deep Learning for Human Sensing
Lex Fridman
MIT AGI: Artificial General Intelligence
Lex Fridman
MIT AGI: Building machines that see, learn, and think like people (Josh Tenenbaum)
Lex Fridman
Ray Kurzweil: Future of Intelligence | MIT 6.S099: Artificial General Intelligence (AGI)
Lex Fridman
Sacha Arnoud, Director of Engineering, Waymo - MIT Self-Driving Cars
Lex Fridman
Lisa Feldman Barrett: How the Brain Creates Emotions | MIT Artificial General Intelligence (AGI)
Lex Fridman
Stephen Wolfram: Computational Universe | MIT 6.S099: Artificial General Intelligence (AGI)
Lex Fridman
Emilio Frazzoli, CTO, nuTonomy - MIT Self-Driving Cars
Lex Fridman
Sterling Anderson, Co-Founder, Aurora - MIT Self-Driving Cars
Lex Fridman
MIT AGI: Cognitive Architecture (Nate Derbinsky)
Lex Fridman
MIT Advanced Vehicle Technology Study (MIT-AVT)
Lex Fridman
MIT-AVT: Data Collection Device (for Large-Scale Semi-Autonomous Driving)
Lex Fridman
Geoffrey Hinton: What are you excited about in deep learning?
Lex Fridman
Ilya Sutskever: OpenAI Meta-Learning and Self-Play | MIT Artificial General Intelligence (AGI)
Lex Fridman
Comfortably Numb Solo | Pink Floyd Cover by Lex Fridman
Lex Fridman
Yoshua Bengio: Deep Learning | Lex Fridman Podcast #4
Lex Fridman
Jeff Atwood: Stack Overflow and Coding Horror | Lex Fridman Podcast #7
Lex Fridman
Eric Schmidt: Google | Lex Fridman Podcast #8
Lex Fridman
Pieter Abbeel: Deep Reinforcement Learning | Lex Fridman Podcast #10
Lex Fridman
Deep Learning Basics: Introduction and Overview
Lex Fridman
Deep Learning State of the Art (2019)
Lex Fridman
MIT 6.S091: Introduction to Deep Reinforcement Learning (Deep RL)
Lex Fridman
Self-Driving Cars: State of the Art (2019)
Lex Fridman
Drago Anguelov (Waymo) - MIT Self-Driving Cars
Lex Fridman
Oliver Cameron (CEO, Voyage) - MIT Self-Driving Cars
Lex Fridman
Karl Iagnemma & Oscar Beijbom (Aptiv Autonomous Mobility) - MIT Self-Driving Cars
Lex Fridman
Leslie Kaelbling: Reinforcement Learning, Planning, and Robotics | Lex Fridman Podcast #15
Lex Fridman
Greg Brockman: OpenAI and AGI | Lex Fridman Podcast #17
Lex Fridman
Ian Goodfellow: Generative Adversarial Networks (GANs) | Lex Fridman Podcast #19
Lex Fridman
MIT 6.S093: Introduction to Human-Centered Artificial Intelligence (AI)
Lex Fridman
Chris Lattner: Compilers, LLVM, Swift, TPU, and ML Accelerators | Lex Fridman Podcast #21
Lex Fridman
Rajat Monga: TensorFlow | Lex Fridman Podcast #22
Lex Fridman
Gavin Miller: Adobe Research | Lex Fridman Podcast #23
Lex Fridman
More on: Algorithm Basics
View skill →
Related AI Lessons
⚡
⚡
⚡
⚡
The ABCs of reading medical research and review papers these days
Medium · LLM
#1 DevLog Meta-research: I Got Tired of Tab Chaos While Reading Research Papers.
Dev.to AI
How to Set Up a Karpathy-Style Wiki for Your Research Field
Medium · AI
The Non-Optimality of Scientific Knowledge: Path Dependence, Lock-In, and The Local Minimum Trap
ArXiv cs.AI
Chapters (21)
Introduction
3:50
Geometry
9:46
Visualizing an algorithm
13:00
A beautiful algorithm
18:06
Don Knuth and geeks
22:06
Early days of computers
25:53
Turing Test
30:05
Consciousness
33:22
Combinatorial algorithms
37:42
Edmonds-Karp algorithm
40:22
Algorithmic complexity
50:25
P=NP
54:25
NP-Complete problems
1:10:29
Proving P=NP
1:12:57
Stable marriage problem
1:20:32
Randomized algorithms
1:33:23
Can a hard problem be easy in practice?
1:43:57
Open problems in theoretical computer science
1:46:21
A strange idea in complexity theory
1:50:49
Machine learning
1:56:26
Bioi
🎓
Tutor Explanation
DeepCamp AI