Revision #1 Authors: Eshan Chattopadhyay, Jesse Goodman, David Zuckerman

Accepted on: 4th October 2021 21:55

Downloads: 725

Keywords:

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^{\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).

Major change in presentation, added new result

TR21-106 Authors: Eshan Chattopadhyay, Jesse Goodman, David Zuckerman

Publication: 23rd July 2021 08:15

Downloads: 693

Keywords:

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 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.