License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.40
URN: urn:nbn:de:0030-drops-156366
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15636/
Chattopadhyay, Eshan ;
Goodman, Jesse ;
Zuckerman, David
The Space Complexity of Sampling
Abstract
Recently, there has been exciting progress in understanding the complexity of distributions. Here, the goal is to quantify the resources required to generate (or sample) a distribution. Proving lower bounds in this new setting is more challenging than in the classical setting, and has yielded interesting new techniques and surprising applications. In this work, we initiate a study of the complexity of sampling with limited memory, and obtain the first nontrivial sampling lower bounds against oblivious read-once branching programs (ROBPs).
In our first main result, we show that any distribution sampled by an ROBP of width 2^{Ω(n)} has statistical distance 1-2^{-Ω(n)} from any distribution that is uniform over a good code. More generally, we obtain sampling lower bounds for any list decodable code, which are nearly tight. Previously, such a result was only known for sampling in AC⁰ (Lovett and Viola, CCC'11; Beck, Impagliazzo and Lovett, FOCS'12). As an application of our result, a known connection implies new data structure lower bounds for storing codewords.
In our second main result, we prove a direct product theorem for sampling with ROBPs. Previously, no direct product theorems were known for the task of sampling, for any computational model. A key ingredient in our proof is a simple new lemma about amplifying statistical distance between sequences of somewhat-dependent random variables. Using this lemma, we also obtain a simple new proof of a known lower bound for sampling disjoint sets using two-party communication protocols (Göös and Watson, RANDOM'19).
BibTeX - Entry
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2022.40,
author = {Chattopadhyay, Eshan and Goodman, Jesse and Zuckerman, David},
title = {{The Space Complexity of Sampling}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {40:1--40:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15636},
URN = {urn:nbn:de:0030-drops-156366},
doi = {10.4230/LIPIcs.ITCS.2022.40},
annote = {Keywords: Complexity of distributions, complexity of sampling, extractors, list decodable codes, lower bounds, read-once branching programs, small-space computation}
}
|
Keywords: |
|
Complexity of distributions, complexity of sampling, extractors, list decodable codes, lower bounds, read-once branching programs, small-space computation |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
