Certificates of sparse matrix quasi-randomness, Luca style

For a random CSP instance, a strong refutation is a certificate of a bound on the number of satisfiable clauses. Such certificates are usually obtained by (1) constructing an ad hoc matrix, (2) certifying that this matrix is quasi-random. In the literature, step (2) can come from a Feige-Ofek type argument, from an application of Grothendieck’s inequality, or from a spectral bound obtained with a trace argument. However, these techniques fail to certify the tight bounds one would expect by poly-logarithmic factors. Luca identified this barrier and designed a program to go around it. In this talk, we will discuss how we developed this program. While doing that, we will relive his thoughtful and illuminating way of thinking, communicating and advising.

[Based on: “A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs”, D’Orsi & Trevisan, CCC’23]