MIT professor and Gödel Prize winner Ryan Williams discusses computational complexity theory in an interview that starts with the classic 3SUM LeetCode problem. He explains the O(N²) two-pointer solution and then describes how algorithms beating N² work via group-based finger search with preprocessing. The conversation covers fine-grained complexity theory, reductions between problems like Subset Sum and 2SUM, the Strong Exponential Time Hypothesis (SETH) and why Williams personally doubts it, hot takes on P vs NP (80% confidence they differ), EXP vs NEXP, and NEXP vs coNEXP. Williams also explains his breakthrough result showing any time-T algorithm can be simulated in space √T, building on Cook and Mertz's tree evaluation work using XOR-based memory tricks instead of write-to-blank-only approaches.
