Probability Seminars——Rapid mixing of Glauber dynamics on hypergraph independent set
主 题: Probability Seminars——Rapid mixing of Glauber dynamics on hypergraph independent set
报告人: Dr. Yumeng Zhang (Stanford University)
时 间: 2017-12-25 14:00-15:00
地 点: Room 1418, Sciences Building No. 1
Abstract: Independent sets in hypergraphs can be encoded as 0-1 configurations on the set of vertices such that each hyperedge is adjacent to at least one 0. This model has been studied in the CS community for its large gap between efficient MCMC algorithms (previously d <(k-1)/2) and the conjectured onset of computational hardness (d > O(2^{k/2}) ), where d is the largest degree of vertices and k is the minimum size of hyperedges. In this talk we provide a percolation approach to this model and show that the Glauber dynamics is rapid mixing for d < O(2^{k/2} ), closing the gap up to a multiplicative constant.
This is joint work with Jonathan Hermon and Allan Sly.
