LFCS Seminar: 2 August 2018 - Yitong Yin
Title: Local distributed sampling from locally-defined distribution
Abstract:
A main theme in theory of distributed computing is to understand what makes a locally-defined computation task locally solvable.
We study the problem of sampling from locally-defined joint distributions by local distributed algorithms. We show that for any joint distribution defined by local constraints, as long as a decay of correlation property called strong spatial mixing is satisfied, there exists a distributed Las Vegas algorithm for sampling precisely from the joint distribution within polylogarimic rounds of communications. This is achieved through the following technical contributions, which may be of independent interests:
- We give a local variant of the famous reduction between sampling and counting of Jerrum, Valiant and Vazirani.
- We generalize the variable-framework for the algorithmic Lovász local lemma (LLL) and the LLL-based partial rejection sampling of Guo, Jerrum, and Liu to include rejection sampling with soft filters, and give a local dynamic algorithm for sampling from the target distribution.
Bio: Yitong Yin is a professor in the Department of Computer Science and Technology at Nanjing University, China. He graduated with a PhD in Computer Science from Yale University in 2009. His interests include algorithms for sampling and counting, theory of distributed and parallel computing, and unconditional lower bounds for computation.
-
LFCS Seminar: 2 August 2018 - Yitong Yin
Speaker: Yitong Yin
IF 4.31/4.33