ECCC-Report TR21-106https://eccc.weizmann.ac.il/report/2021/106Comments and Revisions published for TR21-106en-usMon, 04 Oct 2021 21:55:28 +0300
Revision 1
| The Space Complexity of Sampling |
Eshan Chattopadhyay,
Jesse Goodman,
David Zuckerman
https://eccc.weizmann.ac.il/report/2021/106#revision1Recently, 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^{\Omega(n)}$ has statistical distance $1-2^{-\Omega(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$^0$ (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).
Mon, 04 Oct 2021 21:55:28 +0300https://eccc.weizmann.ac.il/report/2021/106#revision1
Paper TR21-106
| The Space Complexity of Sampling |
Eshan Chattopadhyay,
Jesse Goodman,
David Zuckerman
https://eccc.weizmann.ac.il/report/2021/106Recently, 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 prove small-space analogs of several results previously known only for sampling in AC$^0$.
1. We exhibit an explicit boolean function $b:\{0,1\}^n\to\{0,1\}$ that cannot be computed by width $2^{\Omega(n)}$ read-once branching programs (ROBPs), even on average, but such that $(\mathbf{U}_n,b(\mathbf{U}_n))$ can be exactly sampled by ROBPs of width $O(n)$.
2. We exhibit an explicit boolean function $b:\{0,1\}^n\to\{0,1\}$ such that any distribution sampled by an ROBP of width $2^{\Omega(n)}$ has statistical distance $\frac{1}{2}-2^{-\Omega(n)}$ from $(\mathbf{U}_n,b(\mathbf{U}_n))$. We show that any such $b$ witnesses exponentially small correlation bounds against ROBPs, and we extend these results to hold for the unknown-order setting.
3. We show that any distribution sampled by an ROBP of width $2^{\Omega(n)}$ has statistical distance $1-2^{-\Omega(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. Using a known connection, we also obtain data structure lower bounds for storing codewords.
Along the way, we prove a direct product theorem and several equivalence theorems. These tools offer a generic method to construct distributions with strong sampling lower bounds, and translate these lower bounds into correlation bounds against ROBPs. As an application of our direct product theorem, we show a strong complexity separation between sampling with AC$^0$ circuits and sampling with ROBPs.
Fri, 23 Jul 2021 08:15:13 +0300https://eccc.weizmann.ac.il/report/2021/106