Spectral Refutations and Their Applications to Algorithms and Combinatorics - Lecture 2

Explore spectral refutation techniques and their applications to algorithmic and combinatorial problems in this 73-minute lecture by Pravesh Kothari from the International Centre for Theoretical Sciences. Delve into the mathematical foundations of spectral methods and discover how they can be leveraged to solve complex problems in algorithms and combinatorics. Learn about the theoretical underpinnings of spectral refutations and examine their practical applications across various computational domains. Gain insights into the intersection of geometry, probability, and algorithms through this specialized discussion that forms part of a comprehensive workshop bringing together researchers working on problems requiring interdisciplinary approaches. Understand how spectral and convex programming methods contribute to combinatorial optimization, and explore connections to expanders, random walks, and geometric concepts like isoperimetry that have proven fruitful in theoretical computer science.