Spectral Algorithms from Induced Subgraphs of Cayley Graphs

Explore a two-hour computer science seminar where Peter Manohar from the Institute for Advanced Study presents a novel methodology for solving algorithmic and combinatorial problems through spectral analysis of Cayley graphs. Learn about a two-step approach that involves reducing problems to bounding homogeneous degree-q multilinear polynomials and analyzing spectral properties of induced subgraphs known as "Kikuchi graphs." Discover practical applications including algorithms for solving semirandom constraint satisfaction problems, proving near-optimal extremal girth vs. density trade-offs for hypergraphs, improving lower bounds for q-query locally decodable codes, and establishing exponential lower bounds for 3-query locally correctable codes. Gain insights into advanced mathematical concepts at the intersection of discrete mathematics and computer science, presented in both in-person and remote formats.