Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-106 | 22nd July 2021 22:54

The Space Complexity of Sampling



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.

ISSN 1433-8092 | Imprint