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

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.