Hypergraph Rainbow Problems, Kikuchi Matrices, and Local Codes

Abstract

The classical rainbow cycle conjecture of Keevash, Mubayi, Verstrate, and Sudakov says that every properly edge-colored graph of average degree \Omega(log n) contains a "rainbow" cycle, i.e., a cycle with edges of all distinct colors. Recent advances have almost resolved this conjecture up to an additional log log n factor.  

In this talk, I will describe hypergraph variants of the graph rainbow problem and show how they are intimately related to the existence of (linear) locally decodable and locally correctable codes. 
I will then describe the "Kikuchi Matrix Method" to solve such problems - a general principle that converts hypergraph rainbow problems into related graph counterparts. Consequently, we obtain an exponential lower bound on linear 3 query locally correctable codes, a cubic lower bound on 3 query locally decodable codes (LDCs) and more generally, $k^{q/(q-2)}$ lower bound for all $q$-query LDCs. The case of even $q$ was known since 2004, but the best known bounds for odd q$ were obtained by treating a $q$ query code as a $q+1$ query code instead. 

For those familiar with the work in this area, this will be a combinatorial viewpoint on the spectral methods that yield similar results when the code is restricted to be linear. 

Based on joint works with Omar Alrabiah, Arpon Basu, David Munha-Correia, Venkat Guruswami, Tim Hsieh, Peter Manohar, Sidhanth Mohanty, Andrew Lin, and Benny Sudakov