
Computer Science/Discrete Mathematics Seminar II
Spectral Algorithms from Induced Subgraphs of Cayley Graphs
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.
Date & Time
January 28, 2025 | 10:30am – 12:30pm