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
@@kiran0511 you can do podcasts standing up :> Hinton and Jeff Dean would be amazing, but I'm guessing they have very little time (and don't seem to be very interested in doing public appearences outside of Google)
@@captspeedy1899 Based on what? Your gut feeling? At least provide some scientific basis for your assertion. Link some sources etc. saying "X will happen in Y years, mark my words" without anything to back it up is the same as a homeless person holding up a sign saying "The end is nigh".
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 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.
This is brilliant. Complexity, networks, graphs, AI and implications for Social Psychology and Cognitive science. Thanks a lot Lex Fridman and Richard Karp.
I believe that the constrained version of the stable marriage problem Karp is explaining at around 1:18:00 is about the difference between matching a pair and a triple. Pair matching is a problem in P while triple matching is an NP-complete problem
I think it would be interesting to see an episode with Richard Garfield talking about AI, Mathematics and Magic the Gatering, I think it would be a good programme.
"If an elderly but distinguished scientist says that something is possible, he is almost certainly right; but if he says that it is impossible, he is very probably wrong."
Years ago I was the plenary speaker at a AAAI Spring symposium. I summed it up by saying that the talks consisted of old men explaining why various things were impossible interspersed with young men explaining how they had just implemented them.
Very interesting, I used to hate math when I was in school but only because I found it useless and boring , learning by myself allowed me to see the beauty and power of mathematics and is fascinating
Most rational and humbling opinion about AI I have gotten from a Mathematician/Computer Scientist. Unlike, some I am not even remotely fearful of AI. It maybe blissful ignorance, however, I have absolutely no fear of a machine becoming sentient and be able to compete on a human level with even the most uneducated and low IQ among the human population. AI will never be able to reproduce itself or have the range of human emotions or self-awareness as human beings. Even the lowest IQ among us have a human spirit about them along with the capacity to produce off springs that can differ from themselves in ability, ambition, outlook, and approach to life. This produces a diversity of creativity, approach to life and ambition that is more than raw ability to engage in infinite computation in an extremely efficient manner.
This guys explanation on why he is doubtful on AI just doesn’t justify reality. Tech will continue to improve dramatically. Maybe AI won’t exist in his lifetime, but humanity will definitely achieve it.
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.
Upon hearing "Hungarian Algorithm", my mind leapt to "Bohemian Rhapsody." Then, when I heard him describe the Assignment Problem, it occurred to me that the search for a solution to this problem through the application of a computational algorithm is exactly the kind of challenge that would appeal to geeky young men desperate to discern how they could identify girls who might be willing to go out on a date with them.
stable marriage problem is central to the matching algorithm i need to create for my DeepMatch (candidate/company matching) startup. if anyone listening out there has algorithm development expertise and is interested in potentially working with me on this, please reach out : )
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.
@@Paul-fn2wb I suspect it's a sentence similar in spirit to the one I encountered in a science encyclopedia text about topology: "Please lay the tablecloth with a hole facing upwards." Points, as well as holes, simply don't have direction property.
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.
@FeatherFiend jip. Blows the mind. But I think that a lot of people do not realize that we are already part of a bigger organism. It's even in the name Organization, it even has legal standing. It has specialization of components, communication between components, will to survive, natural selection. This goes for both companies and countries.The question to ask is AGI the evolution of a organization (business) or the evolution of a country or the evolution of a human being. I personally think it is just the evolution of a organization.
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?
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
p is not the same as np so this is true if we use binary logic 1 (true) & 0 (false). p is the same as np so this is true if we use antilogic/quantum logic 1=0 (true = false).
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
Thanks for this amazing series.
I’ll
Lex many great professors are growing old each day. Geoffrey Hinton is also one of them please invite him once.
agree!
@@kiran0511 you can do podcasts standing up :> Hinton and Jeff Dean would be amazing, but I'm guessing they have very little time (and don't seem to be very interested in doing public appearences outside of Google)
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.
This is a real science man, authentic talk not like some of the new age ai gurus wannabes.
AGI will happen in the next 10 years. Mark my words
@@captspeedy1899 Maybe but i would like a better justification than the Ray Kurzweil exponential growth crap.
@@captspeedy1899 Based on what? Your gut feeling? At least provide some scientific basis for your assertion. Link some sources etc.
saying "X will happen in Y years, mark my words" without anything to back it up is the same as a homeless person holding up a sign saying "The end is nigh".
capt speedy I know Conor McGregor used to speak like that.
@@captspeedy1899 no, it won't.
As a guy who studies graph theory for purely enthusiasm, tuning into this podcast is giving me goosebumps. Thank you Lex.
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?
Richard Karp is by far one of the pillars of Computer Science, a true titan in the field. What a great podcast!
transportation problem solving are so under appreciated, mix of economics, psychology, behavior, flow ... everything
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.
This is brilliant. Complexity, networks, graphs, AI and implications for Social Psychology and Cognitive science. Thanks a lot Lex Fridman and Richard Karp.
just saw your comment when Prof mentions this
Thank you for continually educating! I appreciate it a lot
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.
You had me at "Reducibility Among Combinatorial Problems"
awesome interview. Most of those concepts are covered in competitive programmers handbook
once again, speaking for the devs in here, THANK YOU for episodes like this one 🙏♥️🤓
This video answered at least 10 questions that I always struggled with. Thanks, Lex!
I truly love computer science related content ❤️❤️
How does this have so few views? Mr karp is a legend
You ask good questions. I like your style. Thanks for your efforts.
These podcasts are amazing! Greetings from Hungary!
Thank you for the great content especially when it comes to computer science
I enjoyed this conversation.
I like listening to the way that Lex's mind works.
It's fascinating.
:-)
I believe that the constrained version of the stable marriage problem Karp is explaining at around 1:18:00 is about the difference between matching a pair and a triple. Pair matching is a problem in P while triple matching is an NP-complete problem
Lex is doing the world a favor by interviewing the giants of computation.
Just fascinating conversation here, especially the mentions concerning testing and human aspects!! Thank-you, gentlemen.
Awesome Lex and Richard, thanks for simple explanations
I suffer from severe insomnia. This helps me fall asleep. I get knocked out during the first 10min
Thank you Lex, this is a useful interview shining lights on path forward for many problems.
Karp.on being a.barker: "Well I wasn't particularly charming but I could be very repetitious and loud." 😂
You the man Lex, keep up the amazing work 🙌🏽
So, 2 ads every 5 minutes? Makes it hard to watch!
ad block is a free browser extension that rids you of all ads on youtube
I really enjoyed listening to this program. Thanks!
xxxxxx 7
I think it would be interesting to see an episode with Richard Garfield talking about AI, Mathematics and Magic the Gatering, I think it would be a good programme.
Maximal flow of likes > 9000
"If an elderly but distinguished scientist says that something is possible, he is almost certainly right; but if he says that it is impossible, he is very probably wrong."
Years ago I was the plenary speaker at a AAAI Spring symposium. I summed it up by saying that the talks consisted of old men explaining why various things were impossible interspersed with young men explaining how they had just implemented them.
Well, I finally understand P = NP problem. Thanks a lot!
maybe it's time for lex merch?
Nice! Loving the programming podcasts.
Very interesting, I used to hate math when I was in school but only because I found it useless and boring , learning by myself allowed me to see the beauty and power of mathematics and is fascinating
Do one Podcast on the new rover Perseverance going to Mars.
Thanks for your works.
Most rational and humbling opinion about AI I have gotten from a Mathematician/Computer Scientist. Unlike, some I am not even remotely fearful of AI. It maybe blissful ignorance, however, I have absolutely no fear of a machine becoming sentient and be able to compete on a human level with even the most uneducated and low IQ among the human population. AI will never be able to reproduce itself or have the range of human emotions or self-awareness as human beings. Even the lowest IQ among us have a human spirit about them along with the capacity to produce off springs that can differ from themselves in ability, ambition, outlook, and approach to life. This produces a diversity of creativity, approach to life and ambition that is more than raw ability to engage in infinite computation in an extremely efficient manner.
This guys explanation on why he is doubtful on AI just doesn’t justify reality. Tech will continue to improve dramatically. Maybe AI won’t exist in his lifetime, but humanity will definitely achieve it.
Karp's work makes me NP-hard
Lol lex talks faster than the guest in this one. Good podcast tho
RUclips definitely needs a second "Like" button.
thank you lex, excellent interview and a so my Richard karp is a so brilliant mind. Great job
I m loving this channel.🤓🤓🤓
You should do an interview with Rich Hickey. As a fellow Lisper I think you'll appreciate him :)
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.
"I don't always sleep, but when I do I choose eightsleep", lol okay
This is superb advertising 😃
*Algorithm: we may have not met yet, but I'm watching you (like recommendation based on what you searched)*
Please invite professor erick demaine from MIT
When are you going to speak to Stephanie Kelton ( The Deficit Myth )?
Just wanted to say, some day u should have Jonathan Blow on this podcast.
It good be great to invite Jim Simons.
Upon hearing "Hungarian Algorithm", my mind leapt to "Bohemian Rhapsody." Then, when I heard him describe the Assignment Problem, it occurred to me that the search for a solution to this problem through the application of a computational algorithm is exactly the kind of challenge that would appeal to geeky young men desperate to discern how they could identify girls who might be willing to go out on a date with them.
P=NP is perpetual motion
Please show a drawing of what you talk about. 4:30.
Karp's 21 NP-complete problems: en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems
Isn't it that if you solve a NP problem it becomes a P problem by being solved.
And then We have p +1
stable marriage problem is central to the matching algorithm i need to create for my DeepMatch (candidate/company matching) startup. if anyone listening out there has algorithm development expertise and is interested in potentially working with me on this, please reach out : )
Do a search on the Stable Match Problem solution source code.
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.
A straight line is the shortest distance between two points, as long as the points are facing each other :))
Sorry, I don't get it, could you explain? Or is it a joke which I don't get either? :D
That's the point!
@@Paul-fn2wb I's a corny joke and explaining it would be pointless.
@@Paul-fn2wb
I suspect it's a sentence similar in spirit to the one I encountered in a science encyclopedia text about topology: "Please lay the tablecloth with a hole facing upwards."
Points, as well as holes, simply don't have direction property.
Wonderful talk, truly wonderful, nonsense guest. Mister Fridman, thank you for you work.
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.
@FeatherFiend jip. Blows the mind. But I think that a lot of people do not realize that we are already part of a bigger organism. It's even in the name Organization, it even has legal standing. It has specialization of components, communication between components, will to survive, natural selection. This goes for both companies and countries.The question to ask is AGI the evolution of a organization (business) or the evolution of a country or the evolution of a human being. I personally think it is just the evolution of a organization.
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?
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
Now please invite Naval Ravikant please
Where are my shirts brother?
Meet you in MIT Lex.
Interesting ⭐
CS > ALL
Geometry problems without drawings suck! ;-)
GPT-3 ....
p is not the same as np so this is true if we use binary logic 1 (true) & 0 (false).
p is the same as np so this is true if we use antilogic/quantum logic 1=0 (true = false).
It sounds like Mr. MagicKarp to me.
This podcast is the prime example of why there's 1.5x playback speed on RUclips :)
Geoffrey Hinton pls
Awesome.
please interview tim roughgarden
I lack “High dimensional intuition”....me neither. Now words have described my failure b
As
So this must all mean the world is definitely flat then?
stable marriage problem = cuckoo hashing, surprisingly
@theartistbk check out canvas paintings of divine consciousness
Переведите на русский плиз
🙏👑 #grateful
❤❤
🇭🇹🧠👍
.
++
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.
++
++