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

On this episode

About this episode

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…