Existence of Thin Trees | Richard M. Karp Distinguished Lecture

Shayan Oveis Gharan of the University of Washington gives an overview of a recent proof of Goddyn's thin tree conjecture, a long-standing problem in graph theory with applications to the asymmetric traveling salesperson problem. The proof, produced by OpenAI, uses tools from spectral graph theory. Refreshments are served at 3 p.m. and registration is required for in-person attendance.