MIT Professor Ryan Williams explores how advanced algorithmic techniques and fine-grained complexity theory can improve upon classic problems like three-sum and SAT, challenging established assumptions such as the Strong Exponential Time Hypothesis. He also shares his groundbreaking work on space-efficient simulations of time-bounded computations and offers advice on pursuing meaningful, impactful research in computer science.
Ryan Williams, an MIT professor and Gödel Prize winner, discusses advanced algorithmic concepts starting with the classic LeetCode problem, three-sum. While the well-known solution runs in O(n²) time using sorting and a two-pointer “finger search” technique, Williams explains that it is possible to do better than this. By partitioning the sorted list into small groups and employing sophisticated data structures and lookup methods, one can accelerate the finger search process, achieving runtimes better than O(n²), such as around O(n^{1.5}). This approach exemplifies how deep theoretical insights can improve even well-studied algorithmic problems.
Williams then delves into fine-grained complexity, a field focused on understanding the exact time complexities of canonical problems and whether their known algorithms are truly optimal. Unlike classical complexity theory, which broadly classifies problems as polynomial or not, fine-grained complexity investigates whether exponents in polynomial runtimes can be improved. He illustrates this with the subset sum problem, showing how it can be reduced to the two-sum problem, enabling faster algorithms than brute force by cleverly partitioning and searching subsets. This nuanced view allows relating problems across complexity classes in ways traditional theory does not.
A significant part of the conversation centers on the Strong Exponential Time Hypothesis (SETH), which posits that SAT problems cannot be solved substantially faster than 2^n time. Williams expresses skepticism about SETH, arguing that while it is a useful hypothesis for guiding research and establishing conditional lower bounds, the history of algorithmic surprises suggests we do not fully understand polynomial-time computation. He explains that believing SETH is false encourages creative algorithmic thinking and research progress, even if the hypothesis remains unproven. The discussion also covers various forms of SAT and their complexities, including k-SAT and circuit SAT, highlighting how problem structure influences algorithmic difficulty.
Williams shares insights from his groundbreaking work on simulating time-bounded computations in significantly less space than previously thought possible. Building on classical results that showed time T computations could be simulated in space T/log T, he achieved a breakthrough by demonstrating simulations in roughly the square root of T space. The key idea involves sophisticated memory management techniques inspired by tree evaluation problems and clever use of bitwise operations like XOR to avoid erasing and rewriting memory destructively. This result challenges long-held assumptions about space-time trade-offs in computation and opens new avenues for complexity theory.
Finally, Williams reflects on his research philosophy and offers advice to aspiring computer scientists. He emphasizes the importance of working on problems where progress is possible regardless of the outcome, creating “win-win” research scenarios. He also encourages continual self-reflection to avoid inertia and to ensure one’s research direction remains meaningful. Williams advocates for the accessibility of complex problems, noting that no special permission is needed to tackle difficult questions in complexity theory. He recommends foundational texts for learning the field and underscores the value of enjoying the intellectual journey, not just the results.