Printable PDF
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

****************************