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. Aug 02 2018 16.00 - Aug 03 2018 17.00 LFCS Seminar: 2 August 2018 - Yitong Yin Speaker: Yitong Yin IF 4.31/4.33
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. Aug 02 2018 16.00 - Aug 03 2018 17.00 LFCS Seminar: 2 August 2018 - Yitong Yin Speaker: Yitong Yin IF 4.31/4.33
