EUVIMEDEUVIMED entdecken
Crossref

SIGACT News Complexity Theory Column 129 Compressing Correlated Randomness

Geoffroy Couteau

ACM SIGACT News · 11.06.2026 · 57 (2) · 37-72

DOI: 10.1145/3819804.3819810 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM SIGACT News, online erschienen am 11.06.2026. Verfasst von Geoffroy Couteau. Die Arbeit nennt 58 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Couteau, G. (2026). SIGACT News Complexity Theory Column 129 Compressing Correlated Randomness. ACM SIGACT News, 57(2), 37-72. https://doi.org/10.1145/3819804.3819810

Vancouver

Couteau G. SIGACT News Complexity Theory Column 129 Compressing Correlated Randomness. ACM SIGACT News. 2026;57(2):37-72. doi:10.1145/3819804.3819810

BibTeX
@article{Couteau2026,
  author = {Couteau, Geoffroy},
  title = {SIGACT News Complexity Theory Column 129 Compressing Correlated Randomness},
  journal = {ACM SIGACT News},
  year = {2026},
  volume = {57},
  number = {2},
  pages = {37--72},
  doi = {10.1145/3819804.3819810}
}
Kostenlos starten →