LFCS seminar: Yitong Yin: Local distributed sampling from locallydefined distribution
—
filed under:
LFCS Seminar,
Upcoming events
What 


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 locallydefined computation task locally solvable.
We study the problem of sampling from locallydefined 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 variableframework for the algorithmic Lovász local lemma (LLL) and the LLLbased 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.