Institute of Information Science, Academia Sinica

The hypergraph Moore bound is an elegant statement that characterizes the extremal trade-off 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 some log factors in the size in a recent work of Guruswami, Kothari and Manohar [GKM21], but their analysis, especially for the case of odd k, is significantly complicated. In this talk, I’ll 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 [GKM21]'s analysis.
Based on joint work with Pravesh K. Kothari (CMU) and Sidhanth Mohanty (Berkeley) (https://arxiv.org/abs/2207.10850).

I am a PhD student in the Computer Science department at Carnegie Mellon University. I am fortunate to be advised by Pravesh Kothari. I am interested in theoretical computer science in general. Recently, I've been thinking about sum-of-squares certification and rounding algorithms for both worst-case and average-case problems, and also a bit of extremal graph theory. More broadly, I'm interested in the sum-of-squares hierarchy, hardness of approximation, and combinatorics.
In the past, I have worked on artificial intelligence and machine learning. I did my undergraduate and masters at Stanford University, where I worked with Fei-Fei Li and Stefano Ermon on machine learning projects. I'd also like to thank Li-Yang Tan at Stanford for sparking my interest in theoretical computer science.
https://jthsieh.github.io/