Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111

I really enjoyed this conversation with Richard. Here's the 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 - Bioinformatics 2:00:37 - Memory of Richard's father

This is a real science man, authentic talk not like some of the new age ai gurus wannabes.

Lex many great professors are growing old each day. Geoffrey Hinton is also one of them please invite him once.

Whenever an older person is in the show I know I'm in for a treat of wisdom. Especially love it when it's computer science related.

As a guy who studies graph theory for purely enthusiasm, tuning into this podcast is giving me goosebumps. Thank you Lex. <3

You know when it's a very intelligent person talking when that person can take really complex tasks and break them down and explain them to anyone. Thanks for the podcast Lex Friedman and Richard Karp!

I have been waiting for this for so long :))). I attended a public lecture by Richard Karp and was in awe the entire time and absolutely loved it. He was so excited, sharp and passionate even at 84 and I derived a better understanding of the nature of problems in theoretical cs and the structure of the field in general.

Hey Lex your podcast is just like the e^x graph which keeps on increasing in the positive direction of the x axis. They are literally amazing. Can you bring Linus Torvalds next?

Thank you for continually educating! I appreciate it a lot

This is brilliant. Complexity, networks, graphs, AI and implications for Social Psychology and Cognitive science. Thanks a lot Lex Fridman and Richard Karp.

transportation problem solving are so under appreciated, mix of economics, psychology, behavior, flow ... everything

Richard Karp is by far one of the pillars of Computer Science, a true titan in the field. What a great podcast!

Thank you Lex for providing an outline to your video! Makes it easy to listen to areas of interest. I wish more video bloggers would do this.

Thank you very much for this interview with Prof. Karp. For me, computational complexity is the most fascinating topic, and it is absolutely great to hear the major contributors talk about it.

You had me at "Reducibility Among Combinatorial Problems"

once again, speaking for the devs in here, THANK YOU for episodes like this one 🙏♥️🤓

How does this have so few views? Mr karp is a legend

This video answered at least 10 questions that I always struggled with. Thanks, Lex!

These podcasts are amazing! Greetings from Hungary!

I suffer from severe insomnia. This helps me fall asleep. I get knocked out during the first 10min