Joint Computer Science Speaking Skills Talk / Theory Lunch Seminar May 10, 2023 12:00pm — 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/ 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/ Add event to Google Add event to iCal
