Gödel Prize Winner contrarian take on P vs NP: "My point is that we really don't understand polynomial time computation as deeply as we think we do.
And there are surprises. Like, all the time in the power of algorithms, people are finding algorithms where it's just ... surprising. Just ... what?
How do you get something that fast?
This just happens over and over. So, yeah, I think that makes me put it at 80%, because the more I think about it, the less I understand it."
@rrwilliams
Video
Ryan Peterman (@ryanlpeterman)
Ryan Williams (@rrwilliams) is a professor at MIT and the winner of the Gödel Prize in theoretical computer science. I interviewed him all about his work starting by asking him a popular Leetcode question (3 SUM).
In this episode:
• Solving Leetcode faster than popular "optimal" solutions
• SAT problems and solvers
• Hot takes on famous open questions
• How to pick good research direction
Where to watch:
• YouTube - piped.video/AaK1SL2i_4Y
• Spotify - open.spotify.com/episode/0JH…
• Apple Podcasts - podcasts.apple.com/us/podcas…
• Transcript - developing.dev/p/mit-complex…
Thank you to the sponsor of this episode for supporting my work:
• WorkOS: makes your app Enterprise Ready with easy to use APIs to add SSO, SCIM, RBAC, and more in just a few lines of code, check them out at workos.com/
Chapters:
00:00 - Intro
00:41 - Asking him a popular Leetcode question
03:54 - Doing better than the popular optimal solution
08:26 - Fine grained complexity
17:00 - A severe strengthening of P vs NP
24:38 - SAT problems and solvers
34:51 - Hot takes on famous open questions
46:57 - Simulating space with time
01:01:02 - Why he solves hard problems
01:02:35 - How to pick good research direction
01:07:14 - Technical book recommendations
01:08:31 - Advice for his younger self
01:11:56 - Outro
Video
— https://nitter.net/ryanlpeterman/status/2071583211210080656#m