中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

A Simple and Sharper Proof of the Hypergraph Moore Bound

:::

A Simple and Sharper Proof of the Hypergraph Moore Bound

  • 講者Jun-Ting (Tim) Hsieh 先生 (美國卡內基美隆大學)
    邀請人:鐘楷閔
  • 時間2023-01-11 (Wed.) 16:10 ~ 18:10
  • 地點資訊所新館101演講廳
摘要
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).
BIO
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/