Spectral Refutations and Their Applications to Algorithms and Combinatorics

Abstract

I will present a method to reduce extremal combinatorial problems to establishing the unsatisfiability of k-sparse linear equations mod 2 (aka k-XOR formulas) with a limited amount of randomness. This latter task is then accomplished by bounding the spectral norm of certain "Kikuchi" matrices built from the k-XOR formulas. In these talks, I will discuss a couple of applications of this method from the following list. 

1. Proving hypergraph Moore bound (Feige's 2008 conjecture) -- the optimal trade-off between the number of equations in a system of k-sparse linear equations modulo 2 and the size of the smallest linear dependent subset. This theorem generalizes the famous irregular Moore bound of Alon, Hoory and Linial (2002) for graphs (equivalently, 2-sparse linear equations mod 2).

2. Proving a cubic lower bound on 3-query locally decodable codes (LDCs), improving on a quadratic lower bound of Kerenedis and de Wolf (2004) and its generalization to q-query locally decodable codes for all odd q,  

 3. Proving an exponential lower bound on linear 3-query locally correctable codes (LCCs). This result establishes a sharp separation between 3-query LCCs and 3-query LDCs that are known to admit a construction with a sub-exponential length. It is also the first result to obtain any super-polynomial lower bound for >2-query local codes. 

Time permitting, I may also discuss applications to strengthening Szemeredi's theorem, which asks for establishing the minimal size of a random subset of integers S such that every dense subset of integers contains a 3-term arithmetic progression with a common difference from S, and the resolution of Hamada's 1970 conjecture on the algebraic rank of binary 4-designs. 

I will include pointers to the many open questions and directions where meaningful progress seems within reach for researchers who may get interested in some of the topics.