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:

  1. Designing algorithms for refuting/solving semirandom and smoothed instances of constraint satisfaction problems;
  2. Proving a near-optimal extremal girth vs. density trade-off for hypergraphs conjectured by Feige;
  3. Obtaining improved lower bounds for q-query locally decodable codes for all odd q;
  4. Proving an exponential lower bound for 3-query locally correctable codes.

Date & Time

January 28, 2025 | 10:30am – 12:30pm

Location

Simonyi 101 and Remote Access