Lower Bounds for Local Codes from Induced Subgraphs of Cayley Graphs

Explore an advanced computer science seminar that delves into novel methodologies for solving algorithmic and combinatorial problems through the analysis of Cayley graphs and polynomial maximization techniques. Learn how to approach complex problem-solving by reducing challenges to bounding homogeneous degree-q multilinear polynomials and examining spectral properties of induced subgraphs known as "Kikuchi graphs" on the hypercube. Discover two significant applications of this methodology: the development of improved lower bounds for q-query locally decodable codes for odd q values, and the establishment of exponential lower bounds for 3-query locally correctable codes. Gain insights from Peter Manohar's expertise in theoretical computer science as he presents these advanced concepts in a comprehensive two-hour session at the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar II.