Thursday, November 21, 2024
Latest:
Consciousness Videos

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

Lex Fridman



Lex Fridman

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 – Bioinformatics
2:00:37 – Memory of Richard’s father

CONNECT:
– Subscribe to this YouTube channel
– Twitter: https://twitter.com/lexfridman
– LinkedIn: https://www.linkedin.com/in/lexfridman
– Facebook: https://www.facebook.com/LexFridmanPage
– Instagram: https://www.instagram.com/lexfridman
– Medium: https://medium.com/@lexfridman
– Support on Patreon: https://www.patreon.com/lexfridman

Source

Similar Posts

49 thoughts on “Richard Karp: Algorithms and Computational Complexity | Lex Fridman Podcast #111”

  1. 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

  3. Would love it but…. YT has nonstop ads every couple minutes. Exact opposite of the claim at the beginning about ads only at the start.

  7. i usually enjoy the podcast, but this time the questions could be answered by a bachelor student in CS very easily. I think it was a waste of Richard Karp. Maybe making a voting system?

  18. I of course think AGI is inevitable, Single Cell organism builds Multi Cellular organism eventually builds a brain, which eventually evolve into Self Consciousness which eventually evolve into Super Consciousness. I thin AGI is just part of natural evolution.

  19. I think it is really important to understand machines do not have to have Artificial General Intelligence for AI to be a thread to our existence, nor do they need self consciousness. An AI with mastery of a very small domain and enough control can effectively end the human race. (Eg. Military Strategy) The problem with AGI is just much worse and the way I see it is that the moment AGI exist it will be impossible to stop it.

  21. I like how Alex seems to completely miss the first two beautiful examples that the guest presents to him, yet he is perfectly polite and the conversation goes as if there is a perfect understanding between the two.

  34. being from eastern europe, when you say Lex Fridman withouth the "i"( how you hear, not how you write it) it was strange to understand what do you mean .. I always forget this strange thing in english when they say "i" and they refer to "e" and when they say "ei" and the refer to "a" or "i" ?! hopefully a AGI will find this strange too

  41. Matching boys with girls? "That's homophobic!"
    Matching men with jobs? "That's sexist!"
    "Old white male strikes again…"
    I know, I know, this is not the place for that. I'm showing myself the door.

  44. Many CONFUSE Intelligence with LIFE.
    There is NO Such thing as A.I…. It is either an Intelligent Program or it isn't ! Period…. Intelligence comes in many different forms, but with human designed Intelligent systems, DOUBLE LOGIC has Crossed over from humans into these systems…. This is because human 'THOUGHT' and 'REASON", is adversely affected, by the Presence of DOUBLE LOGIC in the human GENOME Construct… As the old saying goes in Math, "Rubbish in, Rubbish out" ! Period…..

  48. 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?

Comments are closed.

WP2Social Auto Publish Powered By : XYZScripts.com