Lower Bounds for Local Codes from Induced Subgraphs of Cayley Graphs

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”.

In this talk, we will focus on the following two applications of this method:

(1) Obtaining polynomially improved lower bounds for q-query locally decodable codes for all odd q;

(2) Proving an exponential lower bound for 3-query locally correctable codes.