Title: Refuting semirandom CSPs via spectral graph theory techniques
| Speaker: | Arkaprava Choudhury |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract:
: In this talk, we will consider recent spectral techniques, developed by [HKM23] and [GKM22], for combinatorial and algorithmic problems. We shall focus, in particular, on designing algorithms for refuting semirandom instances of constraint satisfaction problems. The main component of the talk is a reduction to studying spectral properties of so-called "Kikuchi graphs" corresponding to a system of homogeneous degree-q multilinear polynomials.
No prerequisites in spectral graph theory beyond basic linear algebra are assumed.
[HKM23]: A simple and sharper proof of the hypergraph Moore bound
[GKM22]: Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random"