Twitter/X

Ryan Peterman interviewed MIT professor and Gödel Prize winner Ryan Williams, who…

2026-07-05 · 18:34 UTC ·@ryanlpeterman ·1 min read

Brief

Ryan Peterman's interview with MIT professor and Gödel Prize winner Ryan Williams presents techniques that can solve 3SUM faster than O(n^2), pointing to the 2014 paper (arXiv:1404.0799). The hour-long episode (YouTube/Spotify/Apple Podcasts) links that result to fine-grained complexity, SAT solvers, a proposed strengthening of P vs NP, and research-advice segments.

Why it matters

Ryan Peterman interviewed MIT professor and Gödel Prize winner Ryan Williams, who explains approaches that solve 3SUM faster than O(n^2) and cites the 2014 paper "Threesomes, Degenerates, and Love Triangles" (arXiv:1404.0799).

Key details

  • The episode is chaptered with precise timestamps: 00:41 — LeetCode 3SUM / beating the popular "optimal" solution; 08:26 — fine-grained complexity; 17:00 — a "severe strengthening of P vs NP"; 24:38 — SAT problems and solvers; 46:57 — simulating space with time; 01:02:35 — choosing research direction.
  • The interview is available on YouTube (piped.video/AaK1SL2i_4Y), Spotify, Apple Podcasts, and a transcript (developing.dev/p/mit-complex…), and the episode is sponsored by WorkOS.
Source evidence

Didn't realize 3SUM could be done faster then N^2 until I did this interview

"Threesomes, Degenerates, and Love Triangles", 2014 paper if you want more details: arxiv.org/abs/1404.0799

@rrwilliams Explains some high level approaches in the clip & the pod

Video

Ryan Peterman (@ryanlpeterman)

Ryan Williams (@rrwilliams) 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).

In this episode:

• Solving Leetcode faster than popular "optimal" solutions
• SAT problems and solvers
• Hot takes on famous open questions
• How to pick good research direction

Where to watch:

• YouTube - piped.video/AaK1SL2i_4Y
• Spotify - open.spotify.com/episode/0JH…
• Apple Podcasts - podcasts.apple.com/us/podcas…
• Transcript - developing.dev/p/mit-complex…

Thank you to the sponsor of this episode 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/

Chapters:

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

Video

— https://nitter.net/ryanlpeterman/status/2071583211210080656#m