MIT Complexity Theorist: Why You Can Do Better Than “Optimal” On Leetcode & SAT | Ryan Williams
About this episode
Ryan Peterman interviews MIT professor Ryan Williams about complexity theory and algorithm performance.
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…
Sponsors
WorkOS
More episodes of The Peterman Pod
- Creator of OCaml: Functional Programming, Formal Verification, Programming Languages | Xavier Leroy
- Turing Award Winner: TPU vs GPU vs CPU, Computer Architecture, RISC vs CISC | David Patterson
- Turing Award Winner: NSA, Public Key Cryptography, Crypto Wars | Martin Hellman
- OpenAI Eng & Dev Tools Founder: How Software Engineering Is Changing | Charlie Marsh
- Google DeepMind Pre-Training Lead: How To Land a Job at a Frontier Lab | Vlad Feinberg
Explore listener stats, chart rankings, contacts and more on the The Peterman Pod podcast page.