Show notes
Ryan Williams 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).Correction: In this podcast I say "lower bound" when I mean "upper bound" and vice versa. Was speaking using the intuition that lower is better for running time. In reality, the accurate usage is:"Lower bound" = A proven floor for a problem e.g. "no algorithm can possibly be faster""Upper bound" = A proven ceiling for a specific solution e.g. "there exists an algorithm this fast"Professor Williams answers as if I spoke accurately so the error didn't impact the flow of conversation. Just a correction for the record• My ergonomic keyboard project I mentioned, you can follow along here: https://read.compose.llc/• The Kickstarter page for it: https://www.kickstarter.com/projects/ryanlpeterman/compose-simple-ergonomics-beautifully-donePodcast links:• YouTube: https://youtu.be/AaK1SL2i_4Y• Apple: https://podcasts.apple.com/us/podcast/the-peterman-pod/id1777363835• Transcript: https://www.developing.dev/p/mit-complexity-theorist-on-leetcodeThank you to this episode's sponsor 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 https://workos.com/Timestamps:(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) OutroWhere to find Ryan:• Wikipedia: https://en.wikipedia.org/wiki/Ryan_Williams_(computer_scientist)• Website: https://people.csail.mit.edu/rrw/• LinkedIn: https://www.linkedin.com/in/r-ryan-williams-a1b534a/• X/Twitter: https://twitter.com/rrwilliamsWhere to find Ryan:• Newsletter: https://www.developing.dev/• X/Twitter: https://x.com/ryanlpeterman• LinkedIn: https://www.linkedin.com/in/ryanlpeterman/• Threads: https://www.threads.com/@ryanlpeterman• Instagram: https://www.instagram.com/ryanlpeterman• TikTok: https://www.tiktok.com/@ryanlpetermanReferenced in this episode:• Some Estimated Likelihoods for Computational Complexity: https://people.csail.mit.edu/rrw/likelihoods.pdf• Simulating Time with Square-Root Space: https://arxiv.org/abs/2502.17779• Cook and Mertz's tree evaluation paper: https://dl.acm.org/doi/10.1145/3618260.3649664
