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

<p>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).</p><p><br></p><p>Correction: In this podcast I say &quot;lower bound&quot; when I mean &quot;upper bound&quot; and vice versa. Was speaking using the intuition that lower is better for running time. In reality, the accurate usage is:</p><p><br></p><p>&quot;Lower bound&quot; = A proven floor for a problem e.g. &quot;no algorithm can possibly be faster&quot;</p><p>&quot;Upper bound&quot; = A proven ceiling for a specific solution e.g. &quot;there exists an algorithm this fast&quot;</p><p><br></p><p>Professor Williams answers as if I spoke accurately so the error didn&#39;t impact the flow of conversation. Just a correction for the record</p><p><br></p><p>• My ergonomic keyboard project I mentioned, you can follow along here: https://read.compose.llc/</p><p>• The Kickstarter page for it: https://www.kickstarter.com/projects/ryanlpeterman/compose-simple-ergonomics-beautifully-done</p><p><br></p><p>Podcast links:</p><p><br></p><p>• YouTube: https://youtu.be/AaK1SL2i_4Y</p><p>• Apple: https://podcasts.apple.com/us/podcast/the-peterman-pod/id1777363835</p><p>• Transcript: https://www.developing.dev/p/mit-complexity-theorist-on-leetcode</p><p><br></p><p>Thank you to this episode&#39;s sponsor for supporting my work:</p><p><br></p><p>• 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/</p><p><br></p><p>Timestamps:</p><p><br></p><p>(00:00) Intro</p><p>(00:41) Asking him a popular Leetcode question</p><p>(03:54) Doing better than the popular optimal solution</p><p>(08:26) Fine grained complexity</p><p>(17:00) A severe strengthening of P vs NP</p><p>(24:38) SAT problems and solvers</p><p>(34:51) Hot takes on famous open questions</p><p>(46:57) Simulating space with time</p><p>(01:01:02) Why he solves hard problems</p><p>(01:02:35) How to pick good research direction</p><p>(01:07:14) Technical book recommendations</p><p>(01:08:31) Advice for his younger self</p><p>(01:11:56) Outro</p><p><br></p><p>Where to find Ryan:</p><p><br></p><p>• Wikipedia: https://en.wikipedia.org/wiki/Ryan_Williams_(computer_scientist)</p><p>• Website: https://people.csail.mit.edu/rrw/</p><p>• LinkedIn: https://www.linkedin.com/in/r-ryan-williams-a1b534a/</p><p>• X/Twitter: https://twitter.com/rrwilliams</p><p><br></p><p>Where to find Ryan:</p><p><br></p><p>• Newsletter: https://www.developing.dev/</p><p>• X/Twitter: https://x.com/ryanlpeterman</p><p>• LinkedIn: https://www.linkedin.com/in/ryanlpeterman/</p><p>• Threads: https://www.threads.com/@ryanlpeterman</p><p>• Instagram: https://www.instagram.com/ryanlpeterman</p><p>• TikTok: https://www.tiktok.com/@ryanlpeterman</p><p><br></p><p>Referenced in this episode:</p><p><br></p><p>• Some Estimated Likelihoods for Computational Complexity: https://people.csail.mit.edu/rrw/likelihoods.pdf</p><p>• Simulating Time with Square-Root Space: https://arxiv.org/abs/2502.17779</p><p>• Cook and Mertz&#39;s tree evaluation paper: https://dl.acm.org/doi/10.1145/3618260.3649664</p>