What Can Be Sampled Locally?

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.