2026-07-24T00:34:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15636 2024-03-06T10:55:49Z ddc:004 open_access

The Space Complexity of Sampling Chattopadhyay, Eshan Goodman, Jesse Zuckerman, David Complexity of distributions complexity of sampling extractors list decodable codes lower bounds read-once branching programs small-space computation 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eshan Chattopadhyay and Jesse Goodman and David Zuckerman 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.40 urn:nbn:de:0030-drops-156366 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.40 eng https://creativecommons.org/licenses/by/4.0/legalcode