Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Yitong Yin: Local distributed sampling from locally-defined distribution

LFCS seminar: Yitong Yin: Local distributed sampling from locally-defined distribution

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
When Aug 02, 2018
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal
iCal
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.
Document Actions