Spring 2016

What Can Be Sampled Locally?

Wednesday, Jun. 7, 2017 2:30 pm3:00 pm

Add to Calendar

The local computation of Linial [FOCS'87] and Naor and Stockmeyer [STOC'93] concerns with the question of whether a locally definable distributed computing problem can be solved locally: specifically, for a given local CSP whether a CSP solution can be constructed by a distributed algorithm using local information. In this talk, we consider the problem of sampling a uniform CSP solution by distributed algorithms, and ask whether a locally definable joint distribution can be sampled from locally. Two distributed sampling algorithms and some lower bounds for distributed sampling will be introduced.


PDF icon What Can Be Sampled Locally?4.19 MB