SIGACT News Complexity Theory Column 129 Compressing Correlated Randomness

Is it possible to emulate sampling from an arbitrary efficiently-samplable distribution using an efficient deterministic procedure which is initially fed with a short random seed and increments a counter after each query? Yes, under minimal cryptographic assumptions (the existence of one-way functions) as shown by a sequence of celebrated results in the 80s. Equivalently, one can view this problem as the goal to compress a large number of (seemingly) random samples into a short random seed. But what happens when multiple parties want, given short correlated random seeds distributed in a one-time initialization step, to deterministically and non-interactively obtain correlated samples that cannot be distinguished (even by a subset of the participants themselves) from random samples from a joint distribution? In other words, can cryptography help us compress (seemingly) random correlated samples? Our knowledge of this natural generalization of the problem is considerably more limited, and there is much more that we don't know than we know! Nevertheless, many special cases of this question have been explored in recent (and not so recent) works, motivated in part by numerous applications to other cryptographic tasks. In this article, I provide an introductory exposition of the topic, recasting a number of results originally introduced using various formalisms, under the lens of compressed samplers for multiple parties.