Joint Computer Science Speaking Skills Talk / Theory Lunch Seminar
— 1:00pm
Location:
In Person
-
Gates Hillman 8102
Speaker:
JUN-TING HSIEH
,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://jthsieh.github.io/
A simple and sharper proof of the hypergraph Moore bound
The hypergraph Moore bound is an elegant statement that characterizes the extremal trade-o? between the girth (size of the smallest subhypergraph with all degrees even) and the number of hyperedges in a hypergraph. For graphs (i.e., 2-uniform hypergraphs), a bound tight up to the leading constant was proved in a classical work of Alon, Hoory and Linial. For hypergraphs of uniformity k > 2, an appropriate generalization was conjectured by Feige and resolved, up to an additional log^{4k+1} n factor in the size, in a recent work of Guruswami, Kothari and Manohar [GKM22], but their analysis, especially for the case of odd k, is significantly complicated.
In this talk, I will present a substantially simpler and shorter proof of the hypergraph Moore bound, which also obtains tighter parameters. Our key idea is the use of a new reweighted Kikuchi matrix that allows us to drop several involved steps in GKM's analysis. This is joint work with Pravesh K. Kothari and Sidhanth Mohanty.
Presented as part of the Theory Lunch Seminar
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement
Event Website:
https://www.cs.cmu.edu/~theorylunch/