MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams

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: read.compose.llc
• The Kickstarter page for it: kickstarter.com/projects/ryanlpeterman/compose…

Podcast links:

• YouTube: youtu.be/AaK1SL2i_4Y
• Apple: podcasts.apple.com/us/podcast/the-peterman-pod…
• Transcript: developing.dev/p/mit-complexity-theorist-on-le…

Thank 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 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) Outro

Where to find Ryan:

• Wikipedia: en.wikipedia.org/wiki/Ryan_Williams_(computer_…)
• Website: people.csail.mit.edu/rrw
• LinkedIn: linkedin.com/in/r-ryan-williams-a1b534a
• X/Twitter: twitter.com/rrwilliams

Where to find Ryan:

• Newsletter: developing.dev
• X/Twitter: x.com/ryanlpeterman
• LinkedIn: linkedin.com/in/ryanlpeterman
• Threads: threads.com/@ryanlpeterman
• Instagram: instagram.com/ryanlpeterman
• TikTok: tiktok.com/@ryanlpeterman

Referenced in this episode:

• Some Estimated Likelihoods for Computational Complexity: people.csail.mit.edu/rrw/likelihoods.pdf
• Simulating Time with Square-Root Space: arxiv.org/abs/2502.17779
• Cook and Mertz's tree evaluation paper: dl.acm.org/doi/10.1145/3618260.3649664