Department of Mathematics,
University of California San Diego
****************************
MATH 288 - Probability & Statistics Seminar
Yumeng Zhang
Stanford University
Rapid mixing of Glauber dynamics on hypergraph independent set
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 use a percolation approach to show that the Glauber dynamics is rapid mixing for $d < O(2^{k/2}$), closing the gap up to a multiplicative constant.
Host: Tianyi Zheng
February 8, 2018
9:00 AM
****************************