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

2026-06-29 · 73 min · 24 entities

episode page audio

Asserted relationships

→ references Ryan Williams Computer Scientist person

0.77

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://en.wikipedia.org/wiki/Ryan_Williams_(computer_scientist
→ hosted by Ryan Peterman person

0.55

evidence rules-v5
Feed author/publisher: Ryan Peterman
→ discusses Technology company

0.40

evidence rules-v5
Feed category: Technology
→ references developing.dev website

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://developing.dev/
→ references @Ryanlpeterman website

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://tiktok.com/@ryanlpeterman
→ references Compose Simple Ergonomics Beautifully Done person

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://kickstarter.com/projects/ryanlpeterman/compose-simple-ergonomics-beautifully-done
→ references read.compose.llc company

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://read.compose.llc/
→ references workos.com website

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://workos.com/
→ references AaK1SL2i 4Y website

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://youtu.be/AaK1SL2i_4Y
→ references Mit Complexity Theorist On Leetcode person

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://developing.dev/p/mit-complexity-theorist-on-leetcode
→ references Likelihoods website

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://people.csail.mit.edu/rrw/likelihoods.pdf

Entities found in this episode

websites 10

mentioned developing.dev website

0.45

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://developing.dev/
mentioned @Ryanlpeterman website

0.45

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://threads.com/@ryanlpeterman
mentioned workos.com website

0.45

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://workos.com/
mentioned AaK1SL2i 4Y website

0.45

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://youtu.be/AaK1SL2i_4Y
mentioned Likelihoods website

0.45

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://people.csail.mit.edu/rrw/likelihoods.pdf
references developing.dev website

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://developing.dev/
references @Ryanlpeterman website

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://tiktok.com/@ryanlpeterman
references workos.com website

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://workos.com/
references AaK1SL2i 4Y website

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://youtu.be/AaK1SL2i_4Y
references Likelihoods website

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://people.csail.mit.edu/rrw/likelihoods.pdf

persons 8

mentioned Ryan Williams Computer Scientist person

0.90

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://en.wikipedia.org/wiki/Ryan_Williams_(computer_scientist
references Ryan Williams Computer Scientist person

0.77

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://en.wikipedia.org/wiki/Ryan_Williams_(computer_scientist
mentioned Ryan Peterman person

0.70

evidence rules-v5
Feed author/publisher: Ryan Peterman
hosted by Ryan Peterman person

0.55

evidence rules-v5
Feed author/publisher: Ryan Peterman
mentioned Compose Simple Ergonomics Beautifully Done person

0.45

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://kickstarter.com/projects/ryanlpeterman/compose-simple-ergonomics-beautifully-done
mentioned Mit Complexity Theorist On Leetcode person

0.45

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://developing.dev/p/mit-complexity-theorist-on-leetcode
references Compose Simple Ergonomics Beautifully Done person

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://kickstarter.com/projects/ryanlpeterman/compose-simple-ergonomics-beautifully-done
references Mit Complexity Theorist On Leetcode person

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://developing.dev/p/mit-complexity-theorist-on-leetcode

companys 5

mentioned Technology company

0.50

evidence rules-v5
Feed category: Technology
mentioned read.compose.llc company

0.45

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://read.compose.llc/
discusses Technology company

0.40

evidence rules-v5
Feed category: Technology
references read.compose.llc company

0.38

evidence rules-v5
Link in episode "MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams": https://read.compose.llc/
mentioned MIT company

0.35

evidence rules-v5
MIT

concepts 1

mentioned SAT concept

0.35

evidence rules-v5
SAT

Episode description as stored

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-done Podcast 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-leetcode 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 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) Outro Where 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/rrwilliams Where 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/@ryanlpeterman Referenced 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