Seminar Details
New Spectral Techniques in Algorithms and Coding Theory: the Kikuchi Matrix Method
- Start Date: September 18, 2024
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Peter Manohar - Institute for Advanced Study
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Event Additional Info: <p>The talk will also be broadcast on zoom at this link: <a href="https://rutgers.zoom.us/j/93532717301?pwd=ylbqbkU9wQapXlbaicEg9ao0p3kXKA.1" style="background-color:rgba(0,0,0,0)" target="_blank">https://rutgers.zoom.us/j/93532717301?pwd=ylbqbkU9wQapXlbaicEg9ao0p3kXKA.1</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
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 {0,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 matrices.
The focus of the talk will be on using the method to design optimal algorithms for refuting/solving semirandom and smoothed instances of constraint satisfaction problems. Time permitting, we will also discuss the following two applications:
(1) Proving Feige's conjectured hypergraph Moore bound on the extremal girth vs. density trade-off for hypergraphs;
(2) Proving a cubic lower bound for 3-query locally decodable codes and an exponential lower bound for 3-query locally correctable codes.