Spectral Algorithms from Induced Subgraphs of Cayley Graphs - Peter Manohar

Computer Science/Discrete Mathematics Seminar II 10:30am|Simonyi 101 and Remote Access Topic: Spectral Algorithms from Induced Subgraphs of Cayley Graphs Speaker: Peter Manohar Affiliation: Institute for Advanced Study Date: January 28, 2025  In this talk, we present a new method to solve algorithmic and combinatorial problems by (1) reducing them to bounding the maximum, over x in {-1, 1}^n, of homogeneous degree-q multilinear polynomials, and then (2) bounding the maximum value attained by these polynomials by analyzing the spectral properties of appropriately chosen induced subgraphs of Cayley graphs on the hypercube (and related variants) called “Kikuchi graphs”. We will present the following applications of this method: Designing algorithms for refuting/solving semirandom and smoothed instances of constraint satisfaction problems; Proving a near-optimal extremal girth vs. density trade-off for hypergraphs conjectured by Feige; Obtaining improved lower bounds for q-query locally decodable codes for all odd q; Proving an exponential lower bound for 3-query locally correctable codes.