Local Samplers for Product Distributions

Horacsek, Jordan; Lee, Chin Ho; Shinkar, Igor; Viola, Emanuele; Zhou, Renfei

doi:10.4230/LIPIcs.ICALP.2026.109

Local Samplers for Product Distributions

Jordan Horacsek Simon Fraser University, Burnaby, Canada Chin Ho Lee

North Carolina State University, Raleigh, NC, USA Igor Shinkar

Simon Fraser University, Burnaby, Canada Emanuele Viola

Northeastern University, Boston, MA, USA Renfei Zhou

Carnegie Mellon University, Pittsburgh, PA, USA

Abstract

We obtain several results on sampling product distributions in a local and randomness-efficient fashion:

1.

Let $D=(D_{1},D_{2},\ldots,D_{n})$ be a product distribution where the $D_{i}$ have constant support and have dyadic probability masses (i.e., of the form $a/2^{b}$ where $a, b$ are integers). Then $D$ can be sampled in constant time in the bit-probe model (equivalently, in NC⁰) and randomness complexity $(h(D)+\epsilon)n$ , up to an exponentially small statistical error. The dyadic requirement is necessary.
2.

Every $p$ -biased distribution can be sampled in constant time in the cell-probe model with randomness complexity $h(p)n+\sqrt{n}\cdot\textnormal{polylog}(n)$ , up to a polynomially small statistical distance.
3.

We determine the tradeoffs between locality and statistical distance for sampling the $1/4$ -biased distribution using non-trivial randomness complexity (e.g., $1.99n$ ). For 2 bit probes, essentially no non-trivial approximation is possible; for 3 bit probes, we give a sampler with $1/\textnormal{poly}(n)$ statistical distance and show that this is best possible; finally, 4 bit probes suffice for exponentially small distance.

Our constructions rely on pseudorandom distributions that are bounded uniform on average. These distributions are obtained using various tools from low-density parity-check codes, and recent results on succinct and retrieval data structures by Hu, Liang, Yu, Zhang, and Zhou (STOC 2025).

Keywords and phrases:

Sampling, Succinct data structures, Pseudorandomness

Category:

Track A: Algorithms, Complexity and Games

Funding:

Emanuele Viola: Supported by NSF grant CCF-2430026.

Renfei Zhou: Supported in part by Jane Street Graduate Research Fellowship and MongoDB PhD Fellowship.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Pseudorandomness and derandomization ; Theory of computation

\rightarrow

Data structures design and analysis ; Theory of computation

\rightarrow

Computational complexity and cryptography

Acknowledgements:

We thank the conference reviewers for their comments. Chin Ho Lee is grateful to Cheuk Ting Li for helpful discussion, in particular for pointing out [31] and the references on source simulation.

DOI:

10.4230/LIPIcs.ICALP.2026.109

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Shannon’s source coding theorem [40], see for example [12, Theorem 3.2.1], says that $n$ i.i.d. samples from a source $\mathcal{D}$ can be compressed into about $nH(\mathcal{D})$ bits, from which the samples can be decoded with high probability. In Shannon’s original result, the decoder is not explicit; efficient source decoding algorithms were developed in subsequent works (see, for example, [35] and the references therein).

However, source coding places no requirement on the statistical distance between the decoder’s output distribution and the source distribution. Later, Knuth and Yao [31] initiated the study of “source simulation,” more commonly known as sampling. Formally, given a distribution $\mathcal{D}$ , say supported on $\{0,1\}^{w}$ , the goal is to design a mapping $f\colon\{0,1\}^{m}\to\{0,1\}^{w}$ such that for a uniformly random $\boldsymbol{x}\in\{0,1\}^{m}$ , the distribution of $f(\boldsymbol{x})$ is equal (or close) to $\mathcal{D}$ . Knuth and Yao proved optimal bounds on the expected number of uniform bits required for this task.

By a simple concentration argument, one can extend their result to construct samplers for $n$ i.i.d. samples from any distribution $\mathcal{D}$ with worst-case randomness complexity close to the information-theoretic optimum $nH(\mathcal{D})$ . The sampling question has since been studied extensively in both information theory and computer science theory, leading to time- and space-efficient samplers in various settings. We refer readers to [32, Chapter 9] for a brief survey, and to [16] for a summary of more recent developments.

However, achieving randomness complexity close to $nH(\mathcal{D})$ using samplers that run in constant time per output symbol has proved elusive. Somewhat surprisingly, we show that this is possible in various settings. For example, Theorem 1 establishes such a result in the bit-probe (a.k.a. NC⁰) model for any dyadic source, a restriction that prior work has shown to be necessary.

More broadly, a main motivation for this paper arises from the study of the complexity of distributions. We now elaborate on this perspective and then present our results.

Recent years have witnessed substantial progress on understanding the complexity of sampling distributions, motivated in part by earlier work showing that sampling can be easier than computing. In contrast to the standard task of computing a function, sampling does not require $f$ to output any specific value on a given input $x$ ; rather, the focus is solely on the distribution induced by $f(\boldsymbol{x})$ when $\boldsymbol{x}$ is chosen uniformly at random.

For a concrete example, consider the parity function. While classical results in the 80s [24, 41] showed that $\mathbf{AC}^{0}$ circuits have small correlation with the parity function, the works [2, 8] showed that the uniform distribution on $n$ -bit strings with the same parity can be sampled exactly by the following $2$ -local function on $n-1$ bits:

(x_{1},\ldots,x_{n-1})\mapsto(x_{1},x_{1}\oplus x_{2},x_{2}\oplus x_{3},\ldots% ,x_{n-2}\oplus x_{n-1},x_{n-1}).

Other surprising examples include sampling the inner-product mod $2$ function [27] and random permutations [34, 22, 42]. For background and more discussion we refer the readers to [42].

The work [42] initiated a study of the complexity of sampling using restricted computational models and established several lower bounds. Since then, a large body of works have established many exciting unconditional results on sampling distributions in several restricted models, including local functions [42, 45, 17, 28, 29, 30], small-depth circuits [33, 4], one-way space-bounded computation [9], and communication protocols [20, 50]. By now, this line of research has found a wide range of applications in various areas such as randomness extractors [43, 10, 11], data structures [42, 45, 50, 1], low-distortion embeddings [5, 7], quantum and classical separation [48, 21], and coding theory [39]. In fact, jumping ahead, this work will also further develop some of these connections (in particular, to data structures). We refer the readers to the blogpost [46] for more details on these connections.

In this work, we study the complexity of sampling product distributions. The special case of $p$ -biased distributions on $n$ bits, denoted $\textnormal{Ber}(p)^{n}$ , is already omnipresent in computer science. For example, the complexity of sampling $p$ -biased distributions has been studied in a series of recent works including [45, 17, 28, 29]. Some of the motivation for this line of research comes from a connection with data structures from [42], discussed more below. Such distributions also arise as noise or random restrictions in various areas ranging from distributed computing, to Boolean function analysis, coding theory, randomized algorithms, and learning theory. For example, in cryptography the Learning Parity with Noise (LPN) problem [6] or its cousin the Learning With Errors (LWE) problem [38] are considered standard hardness assumptions. Instantiation of cryptographic primitives based on these assumptions typically requires perturbing a binary vector with $p$ -biased noise. Hence very efficient (or parallel) implementations typically require correspondingly efficient ways to sample such noise. In pseudorandomness, recent approaches to constructing generators involve summing bounded-independence generators with $p$ -biased distributions, see the monograph [25] and the works [13, 14]. Again, efficient implementations of these generators require efficient samplers for $p$ -biased distributions.

Our main interest in this work is to understand the tradeoffs between locality, input length which we also call seed length or randomness complexity, and statistical distance for sampling product distributions.

To illustrate, let us consider the task of sampling the $1/4$ -biased distribution on $n$ bits, denoted $\textnormal{Ber}(1/4)^{n}$ . On the one hand, the distribution $\textnormal{Ber}(1/4)^{n}$ can be sampled with randomness complexity $2n$ and locality $2$ . This trivial construction partitions the $2n$ input bits into $n$ pairs, and for each pair computes AND of the two bits. On the other hand, the result by Knuth and Yao [31] implies that any $p$ -biased distributions on $n$ bits can be sampled with randomness complexity $h(p)n+o_{n}(1)$ , where $h(p)\coloneq p\log_{2}(1/p)+(1-p)\log_{2}(1/(1-p))$ is the binary entropy function, which is best possible. However, their result and follow-up works do not take locality of sampling algorithm into account. It is natural to ask whether one can simultaneously achieve small locality and low randomness complexity. This question was explicitly posed in a blog post [44] nearly a decade ago; yet, to the best of our knowledge, the tradeoffs involved remain poorly understood. In particular, the following basic question has remained open:

Can you sample $\textnormal{Ber}(1/4)^{n}$ with constant locality and randomness complexity

$(h(1/4)+\epsilon)n$ ?

Can you even get randomness complexity $1.99n$ with constant locality?

1.1 Our results

We resolve the aforementioned basic question in the affirmative. Somewhat surprisingly, we show that with constant locality we can sample any product distribution (in particular, $\textnormal{Ber}(1/4)^{n}$ ) with nearly optimal randomness complexity. This result requires the distribution to be dyadic, i.e., all probability masses are of the form $a/2^{b}$ for integers $a, b$ . The dyadic requirement is necessary: for example, $\textnormal{Ber}(1/3)^{n}$ cannot be sampled locally, even approximately. This follows from the techniques in [45], though the result there is stated for the Hamming slice; alternatively, see [28, Theorem 1.10]. Thus, our results illustrate a stark contrast between sampling $\textnormal{Ber}(p)^{n}$ for dyadic and non-dyadic values of $p$ . Henceforth, we denote statistical distance by $\mathrm{dist}$ .

Theorem 1 (Special case of Theorem 8).

Let $D=(D_{1},D_{2},\ldots,D_{n})$ be a product distribution where each $D_{i}$ is dyadic and supported on $\{0,1\}^{w}$ . For every $\epsilon>0$ , there is a $O_{w,\epsilon}(1)$ -local $f$ with input length $H(D)+\epsilon wn$ such that $\mathrm{dist}(f(U),D)\leq e^{-\Omega_{w,\epsilon}(n)}$ .

By increasing the locality to $O(\log n$ ), we can approximate any distribution by a dyadic one and sample any arbitrary product distribution to within distance $1/\textnormal{poly}(n)$ (see Corollary 9).

The above result is in the bit-probe model. Our next result is in the cell-probe model, where the input randomness is organized in words of $O(\log n)$ bits, and one probe reads an entire word. We show how to sample $\textnormal{Ber}(p)^{n}$ with randomness complexity $h(p)n+\widetilde{O}({\sqrt{n}})$ to within distance $1/\textnormal{poly}(n)$ , in constant time.

Theorem 2.

The distribution $\textnormal{Ber}(p)^{n}$ can be sampled using $h(p)n+\sqrt{n}\cdot\textnormal{polylog}(n)$ uniform bits within statistical distance $1/\textnormal{poly}(n)$ with $O(1)$ word-probes.

Returning to the bit-probe model, recall the trivial sampler of $\textnormal{Ber}(1/4)^{n}$ that is $2$ -local and uses randomness complexity $2n$ . We ask ourselves what can be achieved using constant locality and non-trivial randomness complexity $(2-\epsilon)n$ . We determine the tradeoff between locality and statistical distance: For $2$ bit-probes, no non-trivial approximation is possible; for 3 bit-probes, we give a sampler with $1/\textnormal{poly}(n)$ error and show that this is best possible; finally, 4 bit-probes suffice for exponentially small distance. We state these results in two theorems, the first focusing on negative results, the other on positive.

Theorem 3 (Theorem 19 and Theorem 25).

For $\epsilon>0$ and $f\colon\{0,1\}^{(2-\epsilon)n}\to\{0,1\}^{n}$ be any $d$ -local function. We have

\mathrm{dist}(f(U),\textnormal{Ber}(1/4)^{n})\geq\begin{cases}1-e^{-\Omega(n)}% &\text{if $d=2$}\\ n^{-O(1)}&\text{if $d=3$.}\end{cases}

Theorem 4 (Theorem 23 and Theorem 28).

For $d\in\{3,4\}$ , there is an $\epsilon>0$ and a $d$ -local sampler $f\colon\{0,1\}^{(2-\epsilon)n}\to\{0,1\}^{n}$ such that

\mathrm{dist}(f(U),\textnormal{Ber}(1/4)^{n})\leq\begin{cases}n^{-\Omega(1)}&% \text{if $d=3$}\\ e^{-\Omega(n)}&\text{if $d=4$.}\end{cases}

Our constructions are explicit in the following sense. The claimed samplers (viewed, for example, as circuits) can be constructed by an efficient randomized algorithm, with a small error probability. Jumping ahead, the error probability arises from the need of constructing certain matrices (cf. Lemma 11) for which we do not know of a deterministic construction. However, at least in the cell-probe model we also obtain a deterministic construction of the sampler (see full version of this paper).

While we have focused on product distributions, we mention that a body of works has established strong negative results for sampling distributions in NC⁰ or even AC⁰ regardless of the input length of the sampler. For example, [33] has shown the existence of linear maps that cannot be sampled in AC⁰. Still, there remains some interesting open questions. For example, it would be interesting to sample random walks on graphs (equivalently, Markov chains), a problem studied in [47].

1.2 Proof overview

We now give an overview of the proofs. We focus on sampling $\textnormal{Ber}(1/4)^{n}$ , which captures all the key ideas in our arguments.

Broadly speaking, we obtain Theorems 1 and 2 by concatenating independent blocks of local samplers with variable input lengths that are close to optimal on average, followed by sampling their inputs locally and randomness-efficiently. The latter relies on sampling distributions that are bounded-uniform in an average-case sense. Henceforth, we call a sampler for each block a block-sampler.

Overview of Theorem 1

A building block of our construction is a (possibly inefficient) block-sampler of $\textnormal{Ber}(1/4)^{b}$ with expected randomness complexity close to the optimal $h(1/4)b$ . Such construction dates back to the work of Knuth and Yao [31]. To illustrate the basic idea, consider sampling one bit, i.e., $\textnormal{Ber}(1/4)^{1}$ . We can do so as follows. First, read an input bit. If it’s 0, output $0$ ; otherwise, read another input bit and output it. This samples perfectly $\textnormal{Ber}(1/4)^{1}$ . While in the worst case we use a trivial randomness complexity $2$ , the expected number of input bits read is only $1.25$ , which is much better. This idea can be realized using a prefix-free encoding so that the expected number of bits read is close to optimal.

Given such a block-sampler, we divide the $n$ output bits in blocks of length $b=O_{\epsilon}(1)$ , and consider sampling each block with an independent copy of the block-sampler. By concentration inequalities, with high probability over the randomness of the input bits, the actual number of random bits used to sample a typical output is close to optimal.

We next derandomize this construction. To do so, we sample the inputs to the block-samplers pseudorandomly via a local linear transformation. Specifically, we take a nearly optimal number of uniform bits and multiply them by a sparse matrix that expands them into input bits of the block-samplers.

The key property we need from the matrix is that most small subsets of its rows, corresponding to the coordinates read by the block-samplers, are linearly independent. This condition is strictly weaker than bounded uniformity, which requires every small subset of rows to be linearly independent. Indeed, the Plotkin bound implies that no matrix satisfying the stronger requirement can achieve optimal seed length. So exploiting this weaker condition is crucial in our construction.

Although the required matrix property seems relatively basic, we are not aware of any result in the literature that can be applied directly. So, we give a self-contained analysis showing that a suitable random construction satisfies this property with high probability.

Overview of Theorem 2

Theorem 2 is obtained via a new connection between sampling and succinct data structure. While a link between these two areas was already observed in [42] (see Claim 6 below) and used in a number of following works, our connection is different. The work [42] pointed out that a succinct data structure is immediately a non-trivial sampler, but the statistical distance can be quite large and close to 1. This connection can be used to establish data-structure lower bounds from sampling lower bounds that rule out even such large statistical distance, but it is not clear how one can use it to obtain useful samplers, even with statistical distance $1/2$ . Indeed, we are not aware of any construction of samplers that is based on data structure. Moreover, as our target distribution is not uniform on a set, it is not clear we can use any existing data structure directly in a blackbox way. Instead, we leverage and adapt the techniques used in recent exciting progress on the set membership (and dictionary) data structure problems [26], in particular the use of retrieval data structures.

To explain we begin with a key concept, originating in [37] (see also [15]).

Definition 5 (Spillover representation).

Given an injective map from a set $S$ to $\{0,1\}^{M}\times[K]$ , the spillover representation of an element in $S$ is its corresponding element $(m,k)\in\{0,1\}^{M}\times[K]$ , where $k$ is called the spill.

The work [42] observed the following connection between sampling the uniform distribution over a set and membership data structure.

Claim 6.

Suppose a set of $n$ keys in a universe $U$ can be represented by a spillover representation $(m,k)\in\{0,1\}^{M}\times[K]$ with $M+\log_{2}K\leq\log_{2}\binom{U}{n}+\epsilon$ . Then a uniform key can be sampled from $\{0,1\}^{M}\times[K]$ with error $\epsilon$ .

Proof.

The error is at most the probability that a uniform element from $\{0,1\}^{M}\times[K]$ is not a spillover representation of any keys. Using $1-1/x\leq\log_{2}x$ for $x>0$ , this probability is

1-\frac{\binom{U}{n}}{2^{M}\cdot K}\leq\log_{2}\Bigl(\frac{2^{M}\cdot K}{% \binom{U}{n}}\Bigr)\leq\epsilon.\

$\hfill\vartriangleleft$

We divide the $n$ bits into blocks of $B=\textnormal{polylog}(n)$ bits, as opposed to $O_{\epsilon}(1)$ bits in Theorem 1. To sample a block with constant word-probes, we now use a succinct membership data structure by Yu [49]. It shows that one can represent $B$ -bit strings of Hamming weight $s$ by spillover representations in $\{0,1\}^{M}\times[K]$ so that each string can be retrieved using $O(1)$ word-probes to the representation. Moreover, the redundancy $M+\log_{2}K-\log\binom{B}{s}$ is $1/\textnormal{poly}(n)$ small.

A critical point here is that to sample $\textnormal{Ber}(1/4)^{B}$ , the weight $s$ is not fixed, but a random variable distributed according to the binomial distribution $\textnormal{Bin}(B,1/4)$ . Consequently, both $M$ and $K$ are random variables induced by $s$ .

To sample $\textnormal{Ber}(1/4)^{B}$ , as in [26] we encode a distribution $\mathcal{B}$ that is close to $\textnormal{Bin}(B,1/4)$ into the first $O(1)$ words in each representation with a $1/\textnormal{poly}(n)$ increase in redundancy. This gives us a block-sampler for $\textnormal{Ber}(1/4)^{B}$ : we first sample the first $O(1)$ words to determine the Hamming weight $\boldsymbol{s}\sim\mathcal{B}$ , followed by sampling a uniform string of Hamming weight $\boldsymbol{s}$ using the spill representation in $\{0,1\}^{M^{(\boldsymbol{s})}}\times[K^{(\boldsymbol{s})}]$ . One can show that $M^{(\boldsymbol{s})}+\log_{2}K^{(\boldsymbol{s})}\leq h(1/4)B+1/\textnormal{% poly}(n)$ in expectation over $\boldsymbol{s}\sim\mathcal{B}$ . Now we can apply Claim 6 to obtain a $O(1)$ -word-probe block-sampler for $\textnormal{Ber}(1/4)^{B}$ .

Our plan is to concatenate the $L\coloneq n/B$ independent copies of the block-sampler to sample the $n$ bits. However, as the size of a representation depends on $\boldsymbol{s}\sim\mathcal{B}$ , sampling the $L$ representations $(\boldsymbol{m}_{i},\boldsymbol{k}_{i})\sim\{0,1\}^{M^{(\boldsymbol{s}_{i})}}% \times[K^{(\boldsymbol{s}_{i})}]$ together with small redundancy becomes a challenge. The issue here is what we alluded to before. The $M^{(\boldsymbol{s}_{i})}$ and $K^{(\boldsymbol{s}_{i})}$ are both random variables, so we need to put together data structures of varying length, which is not obvious: where are the relevant input bits for a specific output bit?

The work [26] addressed this challenge using augmented retrieval data structure. We will not define it here, but the key observation behind their construction is that the random variable $M^{(\boldsymbol{s})}$ typically is at least $M_{\min}\coloneq\log\binom{B}{B/4-B^{2/3}}=h(1/4)B-\Theta(B^{1/3})$ , which is much larger than its deviation $\Delta_{\max}\coloneq\log_{2}\binom{B}{B/4}-M_{\min}=O(B^{1/3})$ . Based on this observation, [26] constructs random sparse matrices to concatenate the $L$ representations with $\textnormal{polylog}(n)$ redundancy. Here, we use the same random sparse matrices to sample the $L$ spillover representations for the block-samplers. However, unlike [26], our construction does not achieve $\textnormal{polylog}(n)$ redundancy, because in contrast to the data structure setting, a (local) sampler cannot first sample the sizes $M^{(\boldsymbol{s})}$ (and $K^{(\boldsymbol{s})}$ ) for the $L$ block-samplers and then decide which portions of input bits are read by each block-sampler.

Also, the data structure in [26] requires switching between spillover representations over symbols with different alphabet sizes with small redundancy. In the sampling setting, we also have to ensure these transformations also maintain closeness to the uniform distribution (see Lemma 14).

We refer the readers to Section 3.3 for more details.

Overview of Theorem 3 and Theorem 4

Our 2-local lower bound is based on a win-win argument. Given a sampler $f\colon\{0,1\}^{m}\to\{0,1\}^{n}$ where $m=(2-\epsilon)n$ . We consider the bipartite graph representing the input-output dependency of $f$ .

Suppose there is a subset of $m^{\prime}$ inputs which connects to $n^{\prime}\coloneq 100m^{\prime}$ neighbors, then for every fixing of these input bits, $f$ restricted to the $n^{\prime}$ bits is a 1-local, which can be shown to be exponentially far from $\textnormal{Ber}(1/4)^{n^{\prime}}$ , and this remains so after summing over all $2^{m^{\prime}}$ fixings of the inputs.

Therefore, if $m^{\prime}=\Omega(n)$ , then the result follows. Otherwise, by removing these input vertices and their neighbors, we are left with a $2$ -local map from $(2-\Omega(\epsilon))n^{\prime\prime}$ bits to $n^{\prime\prime}=\Omega(n)$ bits where every input has bounded degree. So we can decompose the outputs into $\Omega(n)$ groups so that each group depends on disjoint inputs. We show that each group has some constant distance away from the $1/4$ -biased distribution. So the overall distance is at least $1-e^{-\Omega(n)}$ .

Our 3-local lower bound (Theorem 25) is shown by finding a set of output coordinates of size $k=O(\log(n))$ which depend on at most $2k-1$ inputs. Indeed, by granularity it follows that we see all zeros on these $k$ coordinates with probability either 0 or at least $2^{-(2k-1)}=\frac{2}{4^{k}}$ , while $\textnormal{Ber}(1/4)^{k}$ outputs all zeros with probability $\frac{1}{4^{k}}$ . Therefore, the statistical distance of our sampler to $\textnormal{Ber}(1/4)^{n}$ is at least $\frac{1}{4^{k}}$ . In order to find such a set, we consider the bipartite graph representing the input-output dependency of the sampler. Noting that the degree of each output vertex is at most 3, the problem essentially reduces to finding a cycle of length $O(\log n)$ in any graphs whose average degree is bounded above by 2.

The construction of our $3$ -local and $4$ -local samplers (Theorem 4) is inspired by the recent iterative framework in constructing pseudorandom generators [25]. Recall that the output of the trivial $2$ -local sampler is the bitwise AND $x\wedge_{n}y$ for two independent uniform $n$ -bit strings $x$ and $y$ . The work [23] suggested the following equivalent view of $x\wedge_{n}y$ .

Claim 7.

Let $\boldsymbol{x},\boldsymbol{y}\sim\{0,1\}^{n}$ be independent, where $\boldsymbol{x}$ is uniform. Then

\mathrm{dist}\bigl(\boldsymbol{x}\wedge_{n}\boldsymbol{y},\textnormal{Ber}(1/4% )^{n}\bigr)\leq\Pr_{\boldsymbol{S}\subseteq[n]}\bigl[\text{$\boldsymbol{y}_{% \boldsymbol{S}}$ is not uniform on $\{0,1\}^{\boldsymbol{S}}$}\bigr].

Proof.

We can think of sampling $\textnormal{Ber}(1/4)^{n}$ by first sampling a uniform $\boldsymbol{x}$ follows by sampling an independent uniform string on the subset $\boldsymbol{S}$ of the 1-coordinates of $\boldsymbol{x}$ . $\hfill\vartriangleleft$

Therefore, to get close to $\textnormal{Ber}(1/4)^{n}$ , it suffices for $\boldsymbol{y}$ to be uniform on a uniform subset $\boldsymbol{S}$ of its $n$ coordinates with high probability. To generate such $\boldsymbol{y}$ , our 3-local sampler assigns each $y_{i}$ to two input bits $z_{i},z_{i}^{\prime}$ according to a 3-regular expander graph $G$ , where $y_{i}$ corresponds to the edge $(z_{i},z_{i}^{\prime})$ . Then we let $y_{i}$ be $z_{i}\oplus z_{i}^{\prime}$ . To analyze the construction, we show that a random subgraph of $G$ has no cycle with probability $1-1/\textnormal{poly}(n)$ . That means the $y_{i}$ ’s are uniform when restricted to most subsets chosen by $x$ , and the result follows.

Our 4-local sampler construction follows the same idea. Again, we use $n$ uniform bits to select a random subset $\boldsymbol{S}\subseteq[n]$ . Then to sample $\boldsymbol{y}$ , we use a $3$ -local LDPC code by Gallager [18] instead of an expander. By analyzing the weight distribution of the code, we show that a random subset of rows in the corresponding parity-check matrix is full rank with probability $1-e^{-\Omega(n)}$ .

2 Local sampler for product distributions

In this section, we prove Theorem 1.

Theorem 8.

Let $q$ be an integer and $D_{1},\ldots,D_{n}$ be $n$ distributions on $\{0,1\}^{w}$ , where the probability $D_{i}(s)$ is an integer multiple of $2^{-q}$ for every $i\in[n]$ and $s\in\{0,1\}^{w}$ . Let $D=D_{1}\times\cdots\times D_{n}$ be the product distribution of the $D_{i}$ ’s.

For every $\epsilon>0$ , there exists a sampler $f\colon\{0,1\}^{m}\to(\{0,1\}^{w})^{n}$ with input length $m\coloneq H(D)+\epsilon qn$ and locality $O(\frac{q}{\epsilon^{2}}\log(\frac{1}{\epsilon}))$ such that $\mathrm{dist}(f(U_{m}),D)<2^{-\Omega(\frac{\epsilon^{3}n}{q^{2}})}$ . The sampler $f$ is adaptive, in the sense that for each output query, $f$ makes $O(\frac{q}{\epsilon^{2}}\log(\frac{1}{\epsilon}))$ sequential queries to the inputs, where each query may depend on the previous queries.

The following is an almost immediate corollary from Theorem 8.

Corollary 9.

Let $D_{1},\ldots,D_{n}$ be $n$ distributions on $\{0,1\}^{w}$ for $w=O(\log n)$ . The product distribution $D\coloneq D_{1}\times\cdots\times D_{n}$ can be sampled using $H(D)+O(n\log n)$ bits with locality $O(\log n)$ and error $1/\textnormal{poly}(n)$ .

Proof.

We can approximate each $D_{i}$ with a distribution $D_{i}^{\prime}$ whose probability masses are integer multiples of $2^{-(w+\lceil\log_{2}(n/\gamma)\rceil)}$ such that $\lvert D_{i}(s)-D^{\prime}_{i}(s)\rvert\leq\frac{2\gamma}{n\cdot 2^{w}}$ for all $s\in\{0,1\}^{w}$ , and in particular $\mathrm{dist}(D_{i},D^{\prime}_{i})\leq\gamma/n$ for all $i\in[n]$ (cf. [42, Lemma 5.2]). Setting $\gamma=1/n^{C}$ for a sufficiently large constant $C$ , the two distributions $D$ and $D^{\prime}\coloneq D_{1}^{\prime}\times\cdots\times D_{n}^{\prime}$ are $1/\textnormal{poly}(n)$ -close in total variation distance. Note that for each $i\in[n]$ we have

H(D^{\prime}_{i})-H(D_{i})\leq\sum_{s\in\{0,1\}^{w}}\Big\lvert D^{\prime}_{i}(% s)\cdot\log_{2}\Bigl(\frac{1}{D^{\prime}_{i}(s)}\Bigr)-D_{i}(s)\cdot\log_{2}% \Bigl(\frac{1}{D_{i}(s)}\Bigr)\Big\rvert.

Since $\lvert D_{i}(s)-D^{\prime}_{i}(s)\rvert\leq\frac{2\gamma}{n\cdot 2^{w}}$ , each term in the sum is at most $\frac{2\gamma}{n\cdot 2^{w}}\log_{2}\left(\frac{n\cdot 2^{w}}{2\gamma}\right)$ , and hence

H(D^{\prime}_{i})\leq H(D_{i})+2^{w}\cdot\frac{2\gamma}{n\cdot 2^{w}}\log_{2}% \left(\frac{n\cdot 2^{w}}{2\gamma}\right)=\frac{2\gamma}{n}\cdot\log_{2}\left(% \frac{n\cdot 2^{w}}{2\gamma}\right).

Therefore, $H(D^{\prime})\leq H(D)+1/\textnormal{poly}(n)$ , and the corollary follows by applying Theorem 8 on $D^{\prime}$ . $\hfill\blacktriangleleft$

We now turn to the proof of Theorem 8. We first apply the following lemma, which is a special case of [31], which gives optimal bounds on the average-case randomness complexity of sampling an arbitrary distribution.

Lemma 10 ([31]).

Let $D$ be any distribution on $\{0,1\}^{w}$ , where there is some $q\in\mathbb{N}$ such that $D(s)$ is an integer multiple of $2^{-q}$ for all $s\in\{0,1\}^{w}$ . Then $D$ can be sampled exactly by a decision tree $f\colon\{0,1\}^{q}\to\{0,1\}^{w}$ , where the expected depth of a leaf is at most $H(D)+2$ .

Lemma 10 and its more general statement in [31] follows from an application of Kraft’s inequality. (A proof can be found in [32, Theorem 55].) For the proof of Theorem 8, we also need a sparse matrix with the following properties.

Lemma 11.

Fix $k\in\mathbb{N}$ and a sufficiently small $\alpha>0$ . Let $d\coloneq\lceil\ln(1/\alpha)/\alpha\rceil$ and $m\geq\max\{\frac{k}{1-2h(\alpha)},\alpha n\}$ . Let $\mathcal{S}$ be any distribution supported on subsets $S\subseteq[n]$ of size $k$ . There exists a matrix $M\in\mathbb{F}_{2}^{n\times m}$ with at most $d$ ones in each row, such that if we sample a subset of its rows $\boldsymbol{S}$ according to $\mathcal{S}$ , then the corresponding submatrix $M_{\boldsymbol{S}}\in\mathbb{F}_{2}^{k\times m}$ is full rank with probability at least

\Pr_{\boldsymbol{S}\sim\mathcal{S}}\left[\text{$M_{\boldsymbol{S}}$ is full % rank}\right]\geq 1-2^{-\Omega(\alpha\log(\frac{1}{\alpha})n)}.

$\blacktriangleright$ Remark 12.

In Lemma 11 we are looking for a matrix $M$ such that most subsets of $k$ rows are linearly independent, where most is with respect to the distribution $\mathcal{S}$ . We note that with the required parameters we cannot possibly hope for a binary matrix where any $k$ rows are linearly independent, as such matrix would correspond to a parity-check matrix of a linear error correcting codes with block length $m$ , minimum distance $k$ , and dimension at least $m-k$ , which is impossible over small alphabet (e.g., by Plotkin’s bound, stating that a linear code of length $m$ with minimum distance $k$ has dimension at most $m-2k+o(1)$ ).

The proof of Lemma 11 is available in the full version of the paper.

Proof of Theorem 8.

Divide the $D_{i}$ ’s into $n/t$ blocks each of size $t=\lceil 8/\epsilon\rceil$ . Let $D^{(j)}$ be the product of the $D_{i}$ ’s in the $j$ -th block. Note that $D^{(j)}$ is supported on $\{0,1\}^{tw}$ and its probability mass on each outcome is an integer multiple of $2^{-qt}$ . We first apply Lemma 10 to sample each $D^{(j)}$ independently with a $q t$ -local block-sampler using $q t$ bits. Let $f^{\prime}\colon\{0,1\}^{qn}\to\{0,1\}^{wn}$ be the concatenation of the $n/t$ block-samplers. We will sample the $q n$ -bit input of $f^{\prime}$ pseudorandomly by applying the sparse matrix from Lemma 11 to a seed of some length $m$ .

For each input $z\in\{0,1\}^{qn}$ of $f^{\prime}$ , let $S_{z}\subseteq[qn]$ denote the subset of positions read by $f^{\prime}$ to evaluate $f^{\prime}(z)\in\{0,1\}^{wn}$ . We emphasize that $S_{z}$ are the only positions read by $f^{\prime}$ to evaluate $f^{\prime}(z)$ . Note that $S_{z}$ can be written as $S_{z}=S_{z}^{1}\sqcup\cdots\sqcup S_{z}^{n/t}$ , where $S_{z}^{j}\subseteq\{(j-1)t+1,(j-1)t+2,\dots,jt\}$ is the subset of bits read by the $j$ -th block-sampler. By Lemma 10, for a uniform $\boldsymbol{z}\sim\{0,1\}^{qn}$ , we have $\operatorname{\mathbb{E}}[\lvert S_{\boldsymbol{z}}^{j}\rvert]\leq H(D^{(j)})+2$ for every $j\in[n/t]$ . Therefore,

\displaystyle\operatorname{\mathbb{E}}_{\boldsymbol{z}}\bigl[\lvert S_{% \boldsymbol{z}}\rvert\bigr]\leq\sum_{i=1}^{n/t}H(D^{(j)})+2\cdot(n/t)\leq H(D)% +(\epsilon/4)n.

Let $k\coloneq H(D)+(\epsilon/2)n$ . By Hoeffding’s inequality, we have

\displaystyle\Pr\bigl[\lvert S_{\boldsymbol{z}}\rvert\geq k\bigr]\geq\Pr\bigl[% \lvert S_{\boldsymbol{z}}\rvert\geq\operatorname{\mathbb{E}}_{z}[\lvert S_{z}% \rvert]+\epsilon n/4\bigr]\leq e^{-\Omega\bigl(\frac{(\epsilon n)^{2}}{(n/t)% \cdot(qt)^{2}}\bigr)}\leq e^{-\Omega\bigl(\frac{\epsilon^{3}}{q^{2}}n\bigr)}.

Define $\alpha>0$ so that $\frac{1}{1-2h(\alpha)}=(1+\epsilon/2)$ (and therefore $\alpha=\Theta(\epsilon/\log(1/\epsilon))$ . Let

m\coloneq k\cdot\frac{1}{1-2h(\alpha)}=k\cdot\Bigl(1+\frac{\epsilon}{2}\Bigr)=% \Bigl(H(D)+\frac{\epsilon n}{2}\Bigr)\Bigl(1+\frac{\epsilon}{2}\Bigr)\leq H(D)% +\epsilon qn,

where the last inequality follows from $H(D)\leq\log_{2}(\lvert{\rm supp}(D)\rvert)\leq qn$ .

Let $M$ be the $qn\times m$ matrix obtained by applying Lemma 11 with $\mathcal{S}$ equal to the distribution of $S_{\boldsymbol{z}}$ conditioned on $\lvert S_{\boldsymbol{z}}\rvert\leq k$ and our choice of $\alpha$ . Our sampler $f\colon\{0,1\}^{m}\to\{0,1\}^{wn}$ takes an input $x\in\{0,1\}^{m}$ and output $f^{\prime}(Mx)$ .

Clearly the input length of $f$ is $m=H(D)+\epsilon n$ . The locality of $f$ is at most $qt\cdot d=O(\frac{q}{\epsilon^{2}}\log^{2}\left(\frac{1}{\epsilon}\right))$ , where $d=O(\log(1/\alpha)/\alpha)=O(\log^{2}(1/\epsilon)/\epsilon)$ is row-sparsity of $M$ given by Lemma 11.

We now analyze the error. By Lemma 11, we have

\displaystyle\Pr_{\boldsymbol{z}}\bigl[\text{$M_{S_{\boldsymbol{z}}}$ is full % rank}\mid\lvert S_{\boldsymbol{z}}\rvert\leq k\bigr]\geq 1-2^{-\Omega(\alpha% \log(\frac{1}{\alpha})qn)}\geq 1-2^{-\Omega(\epsilon qn)}.

Let us condition on the event that both $\lvert S_{\boldsymbol{z}}\rvert\leq k$ and $M_{S_{\boldsymbol{z}}}$ is full rank. Then for a uniformly random input $\boldsymbol{x}\in\{0,1\}^{m}$ to $f$ , the $\leq k$ bits in the coordinates in $S_{\boldsymbol{z}}$ of $M\boldsymbol{x}$ are uniformly random, and thus in each of the $n/t$ blocks the output is distributed according to $D^{(j)}$ . Therefore,

\displaystyle\mathrm{dist}\bigl(f(U_{m}),D\bigr)\leq\Pr_{\boldsymbol{z}\sim\{0% ,1\}^{qn}}\bigl[\lvert S_{\boldsymbol{z}}\rvert\geq k\bigr]+2^{-\Omega(% \epsilon qn)}\leq e^{-\Omega(\frac{\epsilon^{3}}{q^{2}}n)},

as required. $\hfill\blacktriangleleft$

3 Sampling $𝒑$ -biased distributions from static dictionary

In this section we prove Theorem 2, restated below.

Theorem 2. [Restated, see original statement.]

The distribution $\textnormal{Ber}(p)^{n}$ can be sampled using $h(p)n+\sqrt{n}\cdot\textnormal{polylog}(n)$ uniform bits within statistical distance $1/\textnormal{poly}(n)$ with $O(1)$ word-probes.

In Section 3.1, we establish several claims that will be used in our construction. In Section 3.2, we show how to construct a local block-sampler with near-optimal average-case randomness complexity. In Section 3.3, we show how to concatenate these block-samplers in a local fashion.

3.1 Changing bases

In this subsection, we establish local transformations between uniform distributions on sequences over different domains with little overheads and errors.

Claim 13.

The uniform distribution over $[K]$ can be sampled by $m$ elements in $[q]$ with error $K/q^{m}$ .

Proof.

We think of $[q]^{m}$ as $\{0,\ldots,q^{m}-1\}$ . Given a uniform $\boldsymbol{u}\sim\{0,\ldots,q^{m}-1\}$ , we output $\lfloor\frac{\boldsymbol{u}}{K}\rfloor$ . The statistical distance is at most the probability that $\boldsymbol{u}$ lies in the last $q^{m}\bmod K$ elements, which is at most $K/q^{m}$ . $\hfill\vartriangleleft$

Lemma 14.

Given $p,q\leq\textnormal{poly}(n)$ , there is a function $f\colon[q]^{m}\to[p]^{n}$ such that

$\blacksquare$

$m\leq n\log_{q}p+O(\log_{q}n)$ ;
$\blacksquare$

each output coordinate depends on $O(\log_{q}n)$ many input coordinates;
$\blacksquare$

for every subset $S\subseteq[n]$ , if the coordinates $f(U)_{S}$ depends on are $\epsilon$ -close to uniform, then $f(U)_{S}$ is $(\epsilon+1/\textnormal{poly}(n))$ -close to uniform over $[p]^{S}$ .

Proof.

We modify the proof in [15, Section 4] as follows. They showed that one can represent $x_{p}\in[p]^{n}$ by a spillover representation $(x_{q},y)\in[q]^{m^{\prime}}\times[K]$ where $K=\textnormal{poly}(n)$ and

m^{\prime}\log_{2}q+\log_{2}K\leq n\log_{2}p+\frac{1}{\textnormal{poly}(n)}.

Moreover, each element of $[p]^{n}$ only depends on $O(\log_{q}n)$ coordinates of $[q]^{m^{\prime}}\times[K]$ . It follow from Claim 6 that the uniform distribution on $[p]^{n}$ can be sampled from the uniform distribution on $[q]^{m^{\prime}}\times[K]$ with error $1/\textnormal{poly}(n)$ , with each output coordinate depending on at most $O(\log_{q}n)$ of the input coordinates. Finally, we use Claim 13 to sample the uniform distribution over $[K]$ using $O(\log_{q}n)$ elements of $[q]$ with error $1/\textnormal{poly}(n)$ . $\hfill\blacktriangleleft$

3.2 Sampling $𝒑$ -biased distributions on polylog bits

In this subsection, we show how to sample $\textnormal{polylog}(n)$ many $p$ -biased bits with $O(1)$ -word probes.

Theorem 15.

Let $B\coloneq\textnormal{polylog}(n)$ and $C>0$ be any constant. The distribution $\textnormal{Ber}(p)^{B}$ can be sampled from $\{0,1\}^{\boldsymbol{M}}\times[\boldsymbol{K}]$ with error $1/\textnormal{poly}(n)$ , where $\boldsymbol{K}\leq\textnormal{poly}(n)$ , with the following properties:

$\blacksquare$

A distribution $\mathcal{B}$ supported on $[pB-B^{2/3},pB+B^{2/3}]$ that is $n^{-\Omega(C)}$ -close to $\textnormal{Bin}(B,p)$ can be sampled using the first $t\coloneq C\log_{2}n$ bits of $\{0,1\}^{\boldsymbol{M}}$ .
$\blacksquare$

Given a sample $\boldsymbol{s}\sim\mathcal{B}$ , the lengths $M^{\boldsymbol{s}}\coloneq\boldsymbol{M}$ and $K^{(\boldsymbol{s})}\coloneq\boldsymbol{K}$ are fixed and

$\operatorname{\mathbb{E}}_{\boldsymbol{s}\sim\mathcal{B}}\Bigl[M^{(\boldsymbol% {s})}+\log_{2}K^{(\boldsymbol{s})}\Bigr]\leq h(p)B+\frac{1}{n^{C}}.$
$\blacksquare$

Given both $\boldsymbol{s}$ and $K^{(\boldsymbol{s})}$ , each output coordinate of a sample can be computed from $O(1)$ many words of $\boldsymbol{m}\sim\{0,1\}^{\boldsymbol{M}}$ .

The proof of Theorem 15 follows [26], where we encode the distribution of $\boldsymbol{s}$ into the succinct data structure in [49] with a small increase in redundancy.

Lemma 16 (Lemma 28 in [49]).

Let $B\coloneq\textnormal{polylog}(n)$ , and $C>0$ be any constant. A size- $s$ subset $S\subseteq[B]$ can be represented by a spillover representation $(m^{\prime},k^{\prime})\in\{0,1\}^{M^{\prime}}\times[K^{\prime}]$ such that

$\blacksquare$

$K^{\prime}=\textnormal{poly}(n)$ ,
$\blacksquare$

$M^{\prime}+\log K\leq\log\binom{B}{s}+O(1/n^{C})$ ,
$\blacksquare$

each query can be answered with $O(1)$ word probes to $m^{\prime}$ and $k^{\prime}$ .

The proof of Theorem 15 is similar to [26, Lemma 4.2]. We include a proof sketch in the full version of the paper.

3.3 Concatenation

In this subsection, we explain how to sample the inputs of the $L=n/B$ copies of the block-sampler in Theorem 15. Specifically, we will sample the $L$ spill representations $(\boldsymbol{m}_{i},\boldsymbol{k}_{i})\in\{0,1\}^{M^{(\boldsymbol{s}_{i})}}% \times[K^{(\boldsymbol{s}_{i})}]$ in a local and randomness-efficient way.

To illustrate the conceptual idea, let us for simplicity consider sampling only the $\boldsymbol{m}_{i}$ ’s but not the $\boldsymbol{k}_{i}$ , using $L\operatorname{\mathbb{E}}[M^{(\boldsymbol{s})}]+\widetilde{O}(\sqrt{n})$ bits.

Recall that in Theorem 15, $\mathcal{B}$ is a distribution that approximates $\textnormal{Bin}(B,p)$ and is supported on $[pB-B^{2/3},pB+B^{2/3}]$ . For every fixed $s$ in ${\rm supp}(\mathcal{B})$ , the sampler will sample from the uniform distribution on $\{0,1\}^{M^{(s)}}\times[K^{(s)}]$ a spill representation of a size- $s$ subset in $[B]$ . Without loss of generality, we will assume $M^{(s)}$ is an integer multiple of the word size $w=O(\log n)$ and $K^{(s)}\geq n^{C}$ for a large enough $C$ . This can be achieved by moving $O(w)$ bits in $M^{(s)}$ to the spill, which can only change the spill size $K^{(s)}$ by a factor of at most $2^{O(w)}\leq\textnormal{poly}(n)$ .

We now make some observations about $M^{(s)}$ for $s\in{\rm supp}(\mathcal{B})$ . Henceforth, we will treat bits as words, and view $\{0,1\}^{M^{(s)}}$ as $W^{(s)}\coloneq\tfrac{M^{(s)}}{w}$ $\mathbb{F}_{2^{w}}$ -elements. Note that we have $W^{(s)}\in[W_{\min},W_{\max}]$ , where

	$\displaystyle W_{\min}$	$\displaystyle\coloneq\frac{1}{w}\log_{2}\binom{B}{pB-B^{2/3}}=h(p)(B/w)-\Theta% (B^{1/3}/w)\text{ and}$
	$\displaystyle W_{\max}$	$\displaystyle\coloneq\frac{1}{w}\log_{2}\binom{B}{pB}\leq h(p)(B/w).$

Thus, we can write $W^{(s)}=W_{\min}+\Delta^{(s)}$ , where $W_{\min}$ does not depend on $s$ and $\Delta^{(s)}\leq\Delta_{\max}\coloneq W_{\max}-W_{\min}=\Theta(B^{1/3})$ . Therefore, we can make the following conclusion on the concatenation of the $L$ samplers:

$\blacksquare$

it always reads a fixed set of $\overline{W}_{\min}\coloneq LW_{\min}$ coordinates;
$\blacksquare$

it reads at most $\overline{\Delta}_{{\rm thr}}\coloneq\sqrt{L\log n}$ additional coordinates with probability $1-1/\textnormal{poly}(n)$ ;
$\blacksquare$

it reads at most $\overline{\Delta}_{\max}\coloneq L\Delta_{\max}$ additional coordinates in the worst-case.

Moreover, the maximum deviation $\overline{\Delta}_{\max}$ is much smaller than $\overline{W}_{\min}$ . Specifically, we have $\overline{\Delta}_{\max}\leq\overline{W}_{\min}/\log n$ . Based on this observation, we can apply the following sparse matrix used in the augmented retrieval data structure in [26] to sample the $W^{(\boldsymbol{s}_{1})}+\cdots+W^{(\boldsymbol{s}_{L})}$ input elements to the $L$ block-samplers.

Lemma 17.

Let $\mathbb{F}$ be a finite field of size at least $n^{C}$ . Let $\boldsymbol{S}\subseteq[\overline{\Delta}_{\max}]$ be a random subset of size at most $\overline{\Delta}_{{\rm thr}}$ . Suppose $\overline{W}_{\min}\geq\overline{\Delta}_{\max}\log n$ . Then there exists a $(\overline{W}_{\min}+\overline{\Delta}_{\max})\times(\overline{W}_{\min}+% \overline{\Delta}_{{\rm thr}})$ matrix $G$ over $\mathbb{F}$ with $O(1)$ nonzeros in every row such that

\Pr_{\boldsymbol{S}}\Bigl[\text{$G_{[\overline{W}_{\min}]\times\boldsymbol{S}}% $ is full rank}\Bigr]\geq 1-\frac{1}{n^{C/2}}.

The parameters in our lemma are slightly different from the one in [26], so, we give a proof sketch in the full version of this paper.

Here the random subset $\boldsymbol{S}$ in Lemma 17 corresponds to the random subset of the $LW_{\max}$ coordinates read by all $L$ samplers modulo their first $W_{\min}$ elements. By concentration bounds, $\boldsymbol{S}$ has size at most $\sqrt{L\log n}$ with high probability. It follows from Lemma 17 that the number of uniform words used by the sampler is $\overline{W}_{\min}+\overline{\Delta}_{\max}\leq L\operatorname{\mathbb{E}}[W^% {(\boldsymbol{s})}]+\widetilde{O}(\sqrt{n})$ , as desired.

We now briefly discuss how to sample the $L$ spills using the same idea. First, we will assume that $K^{(s)}$ is prime and treat $[K^{(s)}]$ as a field, by embedding $[K^{(s)}]$ into the closest prime field, which has little effect on the error and seed length (see Claim 13).

Note that the $K^{(s_{i})}$ ’s depend on $s_{i}$ ’s and therefore are not all identical. Nevertheless, as $\mathcal{B}$ is supported on $[pB-B^{2/3},pB+B^{2/3}]$ , there are at most $2B^{2/3}+1=\textnormal{polylog}(n)$ many possible values for $K^{(s)}$ . Let us denote these values by $K_{1},\ldots,K_{q}$ for some $q\leq 2B^{2/3}+1$ , and define $p_{j}\coloneq\Pr_{\boldsymbol{s}}[K^{(\boldsymbol{s})}=K_{j}]=\sum_{s:K^{(s)}=% K_{j}}\mathcal{B}(s)$ . Let $N_{j}=N_{j}(s_{1},\ldots,s_{L})$ denote the number of $K^{(s_{i})}$ ’s equal to $K_{j}$ . Over the random choice of $\boldsymbol{s}_{1},\ldots,\boldsymbol{s}_{L}\sim\mathcal{B}$ , the random variable $\boldsymbol{N}_{j}$ is distributed close to $\textnormal{Bin}(L,p_{j})$ , and thus is at most $p_{j}L+O(\sqrt{L\log n})$ with probability at least $1-1/\textnormal{poly}(n)$ .

One complication is that $p_{j}L$ can be smaller than $\sqrt{L\log n}$ . So, in order to apply Lemma 17, we will sample the $\boldsymbol{N}_{j}$ $\mathbb{F}_{K^{j}}$ -elements together with a fraction of the $\overline{W}_{\min}$ $\mathbb{F}_{2^{w}}$ -elements. (We will convert the $\mathbb{F}_{2^{w}}$ -elements to $\mathbb{F}_{K_{j}}$ -elements via Lemma 14.)

3.3.1 Proof of Theorem 2

Our goal is to sample random elements

\boldsymbol{w}\coloneq(\boldsymbol{w}_{1},\ldots,\boldsymbol{w}_{L})\in(% \mathbb{F}_{2^{w}}^{W_{\max}})^{L}\quad\text{and}\quad\boldsymbol{k}_{j}\in[K_% {j}]^{L}:j\in[q],

so that with probability $1-1/\textnormal{poly}(n)$ over $(\boldsymbol{s}_{1},\ldots,\boldsymbol{s}_{L})\sim\mathcal{B}^{L}$ , each $\boldsymbol{w}_{i}$ is $1/\textnormal{poly}(n)$ -close to uniform on the first $W^{(\boldsymbol{s}_{i})}$ elements, and $\boldsymbol{k}_{j}$ is $1/\textnormal{poly}(n)$ -close to uniform on the first $\boldsymbol{N}_{j}$ elements, using $h(p)n+\sqrt{n}\cdot\textnormal{polylog}(n)$ uniform bits. Moreover, each output element depends on $O(1)$ words of size $w=O(\log n)$ bits.

We first partition these elements into $q+1$ parts and sample each part individually using Lemma 17. For each block $i\in[L]$ , let $I_{i}$ be the first $W_{\min}=\Theta(B)$ positions of $w_{i}$ , and $\overline{I_{i}}$ its remaining $\Delta_{\max}=W_{\max}-W_{\min}=\Theta(B^{1/3})$ positions. We then partition their union $\bigcup_{i=1}^{L}I_{i}$ into $q+1$ sets $J_{0}\sqcup J_{1}\sqcup\cdots\sqcup J_{q}$ , where $\lvert J_{i}\rvert\coloneq\frac{LW_{\min}}{4q}$ for $i\in[q]$ (and so $\lvert J_{0}\rvert=\frac{3LW_{\min}}{4}$ ). Note that the coordinates in $J_{i}$ ’s are always read by the sampler, and the rest may not be. We will apply Lemma 17 to sample

1.

(Words) the $\mathbb{F}_{2^{w}}$ -elements in $J_{0}$ and $\bigcup_{i=1}^{q}\overline{I_{i}}$ .
2.

(Spills) $[K_{j}]^{L}$ and the $\mathbb{F}_{2^{w}}$ -elements in $J_{j}$ for each $j\in[q]$ .

Let $\overline{W}_{\min}\coloneq LW_{\min}$ and $\overline{W}_{\max}\coloneq LW_{\max}$ .

Sampling the words

Let $\overline{\Delta}_{{\rm wd},\max}\coloneq L\Delta_{\max}$ , $\overline{\Delta}_{{\rm wd},{\rm thr}}\coloneq\sqrt{L\log n}$ , and $\Delta^{(s)}\coloneq W^{(s)}-W_{\min}$ for every $s\in{\rm supp}(\mathcal{B})$ . Note that $\operatorname{\mathbb{E}}[\sum_{i=1}^{L}\Delta^{(\boldsymbol{s}_{i})}]=L% \operatorname{\mathbb{E}}[W^{(\boldsymbol{s})}-W_{\min}]=o(\sqrt{L\log n})$ . By Hoeffding’s inequality, we have

\Pr_{\boldsymbol{s}_{1},\ldots,\boldsymbol{s}_{L}}\Bigl[\sum_{i=1}^{L}\Delta^{% (\boldsymbol{s}_{i})}\leq\overline{\Delta}_{{\rm wd},{\rm thr}}\Bigr]\geq 1-1/% \textnormal{poly}(n).

Conditioned on this event, let $\boldsymbol{S}$ be the subset of coordinates in $\bigcup_{i=1}^{L}\overline{I_{i}}$ (determined by $\boldsymbol{s}_{1},\ldots,\boldsymbol{s}_{L}$ ) that are read by the sampler (in addition to $\bigcup_{i=1}^{L}I_{i}$ ). We have $\lvert\boldsymbol{S}\rvert\leq\overline{\Delta}_{{\rm wd},{\rm thr}}$ , and

\sum_{i=1}^{q}\lvert\overline{I_{i}}\rvert\log n=\overline{\Delta}_{{\rm wd},% \max}\log n\leq\tfrac{3}{4}\overline{W}_{\min}=\lvert T_{0}\rvert.

By Lemma 17, there is a $(\tfrac{3}{4}\overline{W}_{\min}+\overline{\Delta}_{{\rm wd},\max})\times(% \tfrac{3}{4}\overline{W}_{\min}+\overline{\Delta}_{{\rm wd},{\rm thr}})$ matrix $M$ over $\mathbb{F}_{2^{w}}$ with $O(1)$ nonzeros in each row such that for a uniform $\boldsymbol{u}$ , we have

\Pr_{\boldsymbol{S}}\Bigl[\text{$M\boldsymbol{u}$ is uniform on $\bigcup_{i=1}% ^{L}I_{i}\cup\boldsymbol{S}$}\Bigr]\geq 1-1/\textnormal{poly}(n).

Note that $W_{\min}\leq W^{(s)}]$ for any $s\in{\rm supp}(\mathcal{B})$ , and thus $\overline{W}_{\min}\leq L\operatorname{\mathbb{E}}[W^{(\boldsymbol{s})}]$ . Therefore, the number of uniform bits used to sample this part is at most

\displaystyle\Bigl(\frac{3\overline{W}_{\min}}{4}+\overline{\Delta}_{{\rm wd},% {\rm thr}}\Bigr)\cdot w\leq\frac{3L\operatorname{\mathbb{E}}[M^{(\boldsymbol{s% })}]}{4}+\sqrt{L}\log^{3/2}n.

(1)

Sampling the spills

We now explain how to sample the spills and the remaining words. We will use the following result from number theory [3].

Lemma 18.

For every sufficiently large $n$ , there is a prime between $n$ and $n+n^{0.525}$ .

For each $j\in[q]$ , let $\Delta_{j,{\rm thr}}\coloneq p_{j}L+\sqrt{L\log n}$ , and $P_{j}$ be the smallest prime that is at least $K_{j}$ , which, by Lemma 18, is at most $K_{j}+K_{j}^{0.525}$ . The sampling procedure consists of 3 main steps:

1.

use Claim 13 and 14 to sample $[K_{j}]^{L}$ and the $\frac{\overline{W}_{\min}}{4q}$ word-elements by a distribution $D$ over a tuple of $\mathbb{F}_{P_{j}}$ -elements.
2.

use Lemma 17 to sample the distribution $D$ using uniform $\mathbb{F}_{P_{j}}$ elements.
3.

use Lemma 14 to sample these uniform $\mathbb{F}_{P_{j}}$ elements using uniform words.

We now describe each step in more detail. First, by Claim 13, for any subset $S\subseteq[L]$ , if a distribution $\mathcal{D}$ is $\epsilon$ -close to uniform on $\mathbb{F}_{P_{j}}^{S}$ , then $\mathcal{D}$ is $(\epsilon+\delta)$ -close to uniform on $[K_{j}]^{S}$ , where

\displaystyle\delta\leq L\cdot\frac{K_{j}^{0.525}}{K_{j}+K_{j}^{0.525}}\leq 2% \cdot L\cdot K_{j}^{-0.475}\leq 1/\textnormal{poly}(n).

(2)

Next, we apply Lemma 14 to obtain a local-sampler mapping $\mathbb{F}_{P_{j}}^{F_{j}}$ to $\mathbb{F}_{2^{w}}^{\overline{W}_{\min}/(4q)}$ with error $1/\textnormal{poly}(n)$ , where

F_{j}\coloneq\frac{\overline{W}_{\min}}{4q}\cdot\frac{w}{\log_{2}P_{j}}+O(\log% _{P_{j}}n)=\Theta(n/B^{2/3}).

Recall that $\boldsymbol{N}_{j}\sim\textnormal{Bin}(L,p_{j})$ with $\operatorname{\mathbb{E}}[\boldsymbol{N}_{j}]=p_{j}L$ and $\Delta_{j,{\rm thr}}=p_{j}L+\sqrt{L\log n}$ . By Hoeffding’s inequality, we have

\Pr_{\boldsymbol{s}_{1},\ldots,\boldsymbol{s}_{L}}\bigl[\boldsymbol{N}_{j}\leq% \Delta_{j,{\rm thr}}\bigr]\geq 1-1/\textnormal{poly}(n).

Conditioned on this event, let $\boldsymbol{S}\subseteq[L]$ be the coordinates read by the sampler. We have $\lvert\boldsymbol{S}\rvert\leq\Delta_{j,{\rm thr}}$ . Note that $F_{j}\geq L\log L=\Theta(\tfrac{n}{B}\log n)$ . By Lemma 17, there is a $(F_{j}+L)\times(F_{j}+\Delta_{j,{\rm thr}})$ matrix $M$ over $\mathbb{F}_{P_{j}}$ with $O(1)$ nonzero elements in each row such that for a uniform $\boldsymbol{u}\sim\mathbb{F}_{P_{j}}^{F_{j}+\Delta_{j,{\rm thr}}}$ , we have

\Pr_{\boldsymbol{S}}\bigl[\text{$M\boldsymbol{u}$ is uniform on $[F_{j}]\times% \boldsymbol{S}$}\bigr]\geq 1-1/\textnormal{poly}(n).

Finally, we use Lemma 14 again to sample $\boldsymbol{u}$ from $\{0,1\}^{m_{j}}$ with error $1/\textnormal{poly}(n)$ , where

	$\displaystyle m_{j}$	$\displaystyle\leq(F_{j}+\Delta_{j,{\rm thr}})\log_{2}P_{j}+O(\log_{2}n)$
		$\displaystyle\leq\frac{\overline{W}_{\min}}{4q}\cdot w+p_{j}L\log_{2}P_{j}+O(% \sqrt{L}\log_{2}^{3/2}n)$
		$\displaystyle\leq\frac{\overline{W}_{\min}}{4q}\cdot w+p_{j}L\log_{2}K_{j}+O(% \sqrt{L}\log_{2}^{3/2}n).$

Closeness to uniform follows from Lemma 14, and locality follows since each sampler is $O(1)$ word-local, and thus their composition is also $O(1)$ word-local.

We now analyze the number of uniform bits used to sample this part. Observe that $\sum_{j=1}^{L}p_{j}\log_{2}K_{j}=\sum_{s}\mathcal{B}(s)\log_{2}K^{(s)}=% \operatorname{\mathbb{E}}[K^{(\boldsymbol{s})}]$ . Therefore, the number of bits used is

	$\displaystyle\sum_{j=1}^{q}m_{j}$	$\displaystyle\leq\frac{LW_{\min}}{4}\cdot w+L\sum_{j=1}^{q}p_{j}\log_{2}K_{j}+% B^{2/3}\cdot O(\sqrt{L}\log_{2}^{3/2}n)$
		$\displaystyle\leq\frac{L\operatorname{\mathbb{E}}[M^{(\boldsymbol{s})}]}{4}+L% \operatorname{\mathbb{E}}[\log_{2}K^{(\boldsymbol{s})}]+B^{2/3}\cdot O(\sqrt{L% }\log_{2}^{3/2}n).$		(3)

Summing Equations 1 and 3, the number of bits used by the sampler is at most

L\operatorname{\mathbb{E}}[M^{(s)}+\log_{2}K^{(\boldsymbol{s})}]+B^{2/3}\cdot O% (\sqrt{L}\log_{2}^{3/2}n)\leq h(p)n+\sqrt{n}\cdot\textnormal{polylog}(n).

This completes the proof of Theorem 2.

4 A lower bound for a 2-local construction with $m=(2-\epsilon)n$

In this section, we prove Theorem 19, which says that for any $2$ -local mapping with seed length is $(2-\epsilon)n$ , its distance to $\textnormal{Ber}(1/4)^{n}$ approaches 1 as $n$ increases.

Theorem 19.

Let $n\in\mathbb{N}$ be sufficiently large. Fix $\epsilon>0$ , and let $m=(2-\epsilon)n$ . Let $f\colon\{0,1\}^{m}\to\{0,1\}^{n}$ be a 2-local mapping. Then

\mathrm{dist}\bigl(f(U_{m}),\textnormal{Ber}(1/4)^{n}\bigr)\geq 1-\exp(-c% \epsilon n),

for some absolute constant $c>0$ .

Before proving the theorem, we will prove several claims that will be needed later.

Proposition 20.

Let $f\colon\{0,1\}^{m}\to\{0,1\}^{n}$ be a 1-local mapping. Then

\mathrm{dist}\bigl(f(U),\textnormal{Ber}(1/4)^{n}\bigr)\geq 1-2\cdot e^{-n/128}.

Note that since $f$ is 1-local, we may assume without loss of generality that $m\leq n$ .

Proof.

For each $i\in[m]$ corresponding to the input bit $x_{i}$ , let $N(i)$ be the output bits that depend on $x_{i}$ . Note that we may assume without loss of generality that $\lvert N(i)\rvert\geq 1$ for all $i\in[m]$ , as otherwise we can remove the $i$ ’th coordinate. Since $f$ is 1-local, the sets $N(i)$ and $N(i^{\prime})$ are disjoint for $i\neq i^{\prime}$ , and the distributions $f(x_{i})_{|N(i)}$ and $f(x_{i^{\prime}})_{|N(i^{\prime})}$ are independent. Next we consider the following two cases:

\blacksquare

If $m>n/2$ , we may pick for each $i\in[m]$ one output coordinate $j_{i}\in N(i)$ . Note that the corresponding output bit has distribution $\textnormal{Ber}(1/2)$ , and the joint distribution $f(U_{m})_{(j_{i})_{i\in[m]}}$ is $\textnormal{Ber}(1/2)^{m}$ . Thus

	$\displaystyle\mathrm{dist}\bigl(f(U),\textnormal{Ber}(1/4)^{n}\bigr)$	$\displaystyle\geq\mathrm{dist}\bigl(\textnormal{Ber}(1/2)^{m},\textnormal{Ber}% (1/4)^{m}\bigr)$
		$\displaystyle\geq\Pr\bigl[\textnormal{Bin}(m,1/2)\geq 3m/8\bigr]-\Pr\bigl[% \textnormal{Bin}(m,1/4)\geq 3m/8\bigr]$
		$\displaystyle\geq(1-e^{-m/64})-e^{-m/36}\geq 1-2\cdot e^{-m/64}\geq 1-2\cdot e% ^{-n/128}.$

$\blacksquare$

If $m\leq n/2$ , then $\lvert{\rm supp}(f(U_{m}))\rvert\leq 2^{m}\leq 2^{n/2}$ . On the other hand for any subset $A\subseteq\{0,1\}^{n}$ of size at most $2^{m}$ it holds that $\Pr[\textnormal{Ber}(1/4)^{n}\in A]\leq\Pr[\textnormal{Bin}(n,1/4)\leq n/8]$ , as $\textnormal{Ber}(1/4)^{n}$ assigns higher probability to the elements of lower weight and $\binom{n}{\leq n/8}\geq\frac{1}{\sqrt{n}}\cdot 2^{h(1/8)n}\geq 2^{n/2}\geq 2^{m}$ . Therefore, we have

$\mathrm{dist}\bigl(\textnormal{Ber}(1/4)^{n},f(U)\bigr)\geq 1-\Pr\bigl[% \textnormal{Bin}(n,1/4)\leq n/8\bigr]\geq 1-e^{-n/64}.$

This completes the proof of Proposition 20. $\hfill\blacktriangleleft$

Claim 21.

Let $f\colon\{0,1\}^{m}\to\{0,1\}^{2}$ be a 2-local mapping. Let $i\in[m]$ be a coordinate of the input, and let $N(i)$ be the output bits that are influenced by the $i$ ’th input bit. If $\lvert N(i)\rvert\geq 2$ , then $\mathrm{dist}(f(U_{m})_{|N(i)},\textnormal{Ber}(1/4)^{\lvert N(i)\rvert})\geq 1/8$ .

Proof.

Take any two distinct coordinates $j,j^{\prime}\in N(i)$ . These two coordinates depend on at most three input bits, and hence all probabilities of $f(U_{m})_{\{j,j^{\prime}\}}$ are integer multiples of 1/8. On the other hand, the distribution $\textnormal{Ber}(1/4)^{2}$ has probabilities $(1/16,3/16,3/16,9/16)$ , and thus, each possible 2-bit string contributes at least $\frac{1}{8}$ to each term of the summation in the definition of the distance. Therefore $\mathrm{dist}(f(U_{m})_{|N(i)},\textnormal{Ber}(1/4)^{\lvert N(i)\rvert})\geq% \frac{1}{2}\cdot(4\cdot\frac{1}{16})=1/8$ . $\hfill\vartriangleleft$

We are now ready to prove Theorem 19.

Proof of Theorem 19.

Given a 2-local mapping $f\colon\{0,1\}^{m}\to\{0,1\}^{n}$ with $m=(2-\epsilon)n$ , define a bipartite graph $G=(I\cup O,E)$ , where the vertices in $I$ correspond to the $m$ coordinates of the input, $O$ corresponds to the $n$ coordinates of the output, and $(i,o)\in E$ if the $o$ ’th output bit depends on the $i$ ’th input coordinate. That is, $\lvert I\rvert=m$ , $\lvert O\rvert=n$ , and $\lvert E\rvert=2n$ since $f$ is 2-local.

We fix two large constants $C=99$ , and $d=4(C+1)/\epsilon=400/\epsilon$ . Let $I^{*}\subseteq I$ be a maximal subset of $I$ such that $\lvert N(I^{*})\rvert\geq C\lvert I^{*}\rvert$ , and consider the following two cases.

Case 1: $\lvert N(I^{*})\rvert>n/d$ .

In this case, for any fixing of the inputs $(x_{i})_{i\in I^{*}}$ , the mapping $(f_{j})_{j\in N(I^{*})}$ is 1-local. Therefore, conditioning on $(x_{i})_{i\in I^{*}}$ being fixed, by Proposition 20 the 1-local mapping satisfies

\displaystyle\mathrm{dist}\bigl(f(U_{m}),\textnormal{Ber}(1/4)^{n}\bigr)\geq% \mathrm{dist}\bigl(f(U_{I^{*}}),\textnormal{Ber}(1/4)^{\lvert N(I^{*})\rvert}% \bigr)\geq 1-2\cdot e^{-\frac{\lvert N(I^{*})\rvert}{128}}.

Accounting for all $2^{\lvert I^{*}\rvert}$ assignments to the input bits in $I^{*}$ we get

\displaystyle\mathrm{dist}\bigl(f(U_{m}),\textnormal{Ber}(1/4)^{n}\bigr)\geq 1% -2\sum_{s\in\{0,1\}^{\lvert I^{*}\rvert}}2\cdot e^{-\frac{N\lvert(I^{*})\rvert% }{128}}\geq 1-4\cdot 2^{\lvert I^{*}\rvert}\cdot e^{-\frac{\lvert N(I^{*})% \rvert}{128}}.

Next, we use the assumption that $\lvert I^{*}\rvert\leq\lvert N(I^{*})\rvert/C$ and $\lvert N(I^{*})\rvert\geq n/d$ together with our choice of $C=99$ and $d=4(C+1)/\epsilon=400/\epsilon$ to get

$\displaystyle\mathrm{dist}(f(U_{m}),\textnormal{Ber}(1/4)^{n})$	$\displaystyle\geq$	$\displaystyle 1-4\cdot 2^{\lvert N(I^{})\rvert/C}\cdot e^{-\lvert N(I^{})% \rvert/128}$
	$\displaystyle\geq$	$\displaystyle 1-4\cdot e^{-\frac{1/128-\ln(2)/C}{d}n}$
	$\displaystyle\geq$	$\displaystyle 1-\exp(-\Omega(\epsilon n)).$

This proves Theorem 19 in case of $\lvert N(I^{*})\rvert\geq n/d$ .

Case 2: $\lvert N(I^{*})\rvert\leq n/d$ .

In this case our strategy is the following. We will remove $N(I^{*})$ from the output coordinates. The remaining mapping $f^{\prime}\colon\{0,1\}^{m}\to\{0,1\}^{n^{\prime}}$ will satisfy the property that $m<(2-\epsilon/2)n^{\prime}$ and each input coordinate influences at most $C$ output nodes. This will allow us to find a collection $\mathcal{O}$ of $\Omega(\epsilon n)$ disjoint subsets of output coordinates $(O_{i})_{i\in\mathcal{O}}$ such that

1.

$\mathrm{dist}(f(U_{m^{\prime}})_{|O_{i}},\textnormal{Ber}(1/4)^{\lvert O_{i}% \rvert})\geq 1/8$ for all $O_{i}\in\mathcal{O}$ ,
2.

$\left(f(U_{m^{\prime}})_{|O_{i}}\right)_{O_{i}\in\mathcal{O}}$ are jointly independent.

Then, by a Chernoff bound we conclude that $\mathrm{dist}(f(U_{m}),\textnormal{Ber}(1/4)^{n})\geq 1-\exp(-\Omega(\epsilon n))$ . We describe the details below.

Note that by maximality of $I^{*}$ we have $\lvert N(i)\setminus N(I^{*})\rvert\leq C$ for all $i\in I\setminus I^{*}$ . Therefore, by removing $N(I^{*})$ from the set of outputs, we get a graph $G^{\prime}=(I^{\prime}=I,O^{\prime},E^{\prime})$ such that the degree of each $i\in I^{\prime}$ is at most $C$ .

Since we removed at most $n/d=\epsilon n/400$ output vertices, the new graph has $m^{\prime}=(2-\epsilon)n$ inputs and $n^{\prime}\geq(1-\epsilon/400)n$ outputs. Therefore, $m^{\prime}\leq(2-\epsilon^{\prime})n^{\prime}$ for

\epsilon^{\prime}=2-\frac{m^{\prime}}{n^{\prime}}=2-\frac{2-\epsilon}{1-% \epsilon/400}>\epsilon/2.

Therefore, we now have a 2-local mapping $f^{\prime}\colon\{0,1\}^{m=(2-\epsilon^{\prime})n^{\prime}}\to\{0,1\}^{n^{% \prime}}$ with $\epsilon^{\prime}>\epsilon/2$ such that each input coordinate of $f$ influences at most $C$ output bits, and $f^{\prime}$ has the same distribution as $f$ on the remaining output coordinates.

Let $J=\{i\in I^{\prime}:\deg_{G^{\prime}}(i)\geq 2\}$ .

Claim 22.

$\lvert J\rvert\geq\frac{\epsilon^{\prime}}{2C}n^{\prime}$ .

Proof.

The proof is a simple application of Markov’s inequality. Since $\deg(v)\leq C$ for all $i\in I^{\prime}$ , we have

\frac{2n^{\prime}}{(2-\epsilon^{\prime})n^{\prime}}=\operatorname{\mathbb{E}}_% {i\in I^{\prime}}[\deg(i)]\leq\Pr[\deg(i)\leq 1]+C\cdot\Pr[\deg(i)>1]\leq 1+C% \Pr[\deg(i)>1].

Since $\deg(i)$ is an integer, we get $\Pr[\deg(i)\geq 2]=\Pr[\deg(i)>1]\geq\frac{\epsilon^{\prime}}{(2-\epsilon^{% \prime})C}>\frac{\epsilon^{\prime}}{2C}$ , as required. $\hfill\vartriangleleft$ Now, since each input coordinate in $J$ has degree at most $C$ , we can find a subset $K\subseteq J$ of size $\lvert K\rvert\geq\lvert K\rvert/(C+1)$ such that $N(i)$ and $N(i^{\prime})$ do not have common neighbours for all distinct $i,i^{\prime}\in K$ . Indeed, this is achieved by taking any $i\in J$ , adding it to $K$ and removing from $J$ all neighbours of $N(i)$ .

This gives us a collection of input coordinates $K\subseteq I^{\prime}$ of size $\lvert K\rvert\geq\lvert J\rvert/(C+1)\geq\frac{\epsilon^{\prime}}{2C(C+1)}n^{\prime}$ , such that each $i\in K$ has $\deg(i)\geq 2$ and $\left(f(U_{m})_{|N(i)}\right)_{i\in K}$ are jointly independent.

By Claim 21 we have $\mathrm{dist}(f(U_{m})_{|N(i)},\textnormal{Ber}(1/4)^{\lvert N(i)\rvert})\geq 1/8$ for all $i\in K$ . Therefore, applying Chernoff’s bound on $\left(f(U_{m})_{|N(i)}\right)_{i\in K}$ we get

$\displaystyle\mathrm{dist}(f(U_{m}),\textnormal{Ber}(1/4)^{n})$	$\displaystyle\geq$	$\displaystyle\mathrm{dist}(f^{\prime}(U_{m}),\textnormal{Ber}(1/4)^{n^{\prime}})$
	$\displaystyle\geq$	$\displaystyle 1-2e^{-\frac{(1/8)^{2}\lvert K\rvert}{12}}$
	$\displaystyle\geq$	$\displaystyle 1-2e^{-\frac{\epsilon^{\prime}n^{\prime}}{8^{2}\cdot 12\cdot 2C(% C+1)}}$
	$\displaystyle\geq$	$\displaystyle 1-\exp(-\Omega(\epsilon n)).$

This completes the proof of Theorem 19. $\hfill\blacktriangleleft$

5 A 3-local construction with $m=1.99n$ that is $1/{\textup{{poly}}}(n)$ -close to ${\textup{{Ber}}}(1/4)^{n}$

In this section, we show that in contrast to Theorem 19, if we allow the sampler to be 3-local, we can approximate the distribution $\textnormal{Ber}(1/4)^{n}$ within distance of $1/\textnormal{poly}(n)$ , and this is optimal up to constant factor in the exponent.

Theorem 23.

Fix an integer $t\geq 3$ and let $\epsilon=1/3t$ . Let $n\in N$ be sufficiently large and let $m=(2-\epsilon)n$ . Then, there is a 3-local mapping $f\colon\{0,1\}^{m}\to\{0,1\}^{n}$ such that

\mathrm{dist}\bigl(f(U_{m}),\textnormal{Ber}(1/4)^{n}\bigr)\leq\Bigl(\frac{1}{% 2\epsilon n}\Bigr)^{\frac{2}{9\epsilon}-\frac{5}{3}}.

In particular, for $m=(2-1/9)n$ there is a 3-local mapping $f\colon\{0,1\}^{m}\to\{0,1\}^{n}$ such that

\mathrm{dist}\bigl(f(U_{m}),\textnormal{Ber}(1/4)^{n}\bigr)\leq\frac{2}{n^{1/3% }}.

Proof of Theorem 23

We start with a graph $G^{\prime}=(V^{\prime},E^{\prime})$ that is $3$ -regular graph with $k$ vertices and $1.5k$ edges such that the girth of $G^{\prime}$ is $\geq\frac{2}{3}\log_{2}\lvert V^{\prime}\rvert=\frac{2}{3}\log_{2}k$ . Indeed, such graphs exist [36, Theorem 5.13].

Claim 24.

Let $p=2^{-t}$ for some $t\geq 3$ , and let $\boldsymbol{G}^{\prime}_{p}=(V,E_{p})$ be a random subgraph of $G^{\prime}$ obtained by keeping each edge in $E$ with probability $p$ independently. Then $\Pr[\boldsymbol{G}^{\prime}_{p}\text{ has a cycle}]<k^{-\frac{2t-5}{3}}$ .

Proof.

By the assumption, $G^{\prime}$ has no cycle of length $<\frac{2}{3}\log_{2}(k)$ . For any $\ell\geq\frac{2}{3}\log_{2}k$ , the number of cycles of length $\ell$ is at most $k\cdot 3\cdot 2^{\ell-2}$ . Therefore,

\Pr[\text{$\boldsymbol{G}^{\prime}_{p}$ has a cycle of length $\ell$}]\leq k% \cdot 3\cdot 2^{\ell-2}\cdot p^{\ell}=\frac{3k}{4}(2p)^{\ell}.

Taking the union bound over all lengths $\ell>\frac{2}{3}\log_{2}(k)$ , we get

\Pr[\text{$\boldsymbol{G}^{\prime}_{p}$ has a cycle}]<\frac{3k}{4}\cdot\sum_{% \ell=\frac{2}{3}\log_{2}(k)}^{\infty}(2p)^{\ell}=\frac{3k}{4}\cdot\frac{(2p)^{% \frac{2}{3}\log_{2}(k)}}{1-2p}<\frac{1}{k^{\frac{2t-5}{3}}},

(4)

as required. $\hfill\vartriangleleft$

Given the graph $G^{\prime}$ above, we define a graph $G=(V,E)$ by subdividing each edge of $G^{\prime}$ into $t\geq 3$ edges. The number of vertices in $G$ is $\lvert V\rvert=\lvert V^{\prime}\rvert+(t-1)\lvert E^{\prime}\rvert=k+1.5(t-1)% k=(1.5t-0.5)k$ , and the number of edges is $\lvert E\rvert=1.5tk$ .

Let $n=\lvert E\rvert=1.5tk$ and $m=\lvert V\rvert+\lvert E\rvert=(3t-0.5)k=(2-1/3t)n=(2-\epsilon)n$ . Define $g\colon\{0,1\}^{m-n}\to\{0,1\}^{n}$ by $g_{i}(y)=y_{u_{i}}\oplus y_{v_{i}}$ , where $(u_{i},v_{i})$ are the endpoints of the $i$ ’th edge in $G$ . By Claim 7, we have

\mathrm{dist}\bigl(f(U_{m}),\textnormal{Ber}(1/4)^{n}\bigr)\leq\Pr_{% \boldsymbol{S}}[\text{$g(\boldsymbol{y})$ restricted to the coordinates in $% \boldsymbol{S}$ is not uniform}],

where $\boldsymbol{S}$ is a uniform subset of $[n]$ . We will show that

\displaystyle\Pr_{\boldsymbol{S}}[\text{$g(\boldsymbol{y})_{\boldsymbol{S}}$ % is not uniform}]\leq\Pr[\text{$\boldsymbol{G}_{1/2}$ has a cycle}],

(5)

where $\boldsymbol{G}_{1/2}$ is a random subgraph of $G$ obtained by keeping each edge with probability $1/2$ . This proves Theorem 23 by combining ˜24 with the observation that $\Pr[\text{$\boldsymbol{G}_{1/2}$ has a cycle}]=\Pr[\text{$\boldsymbol{G}^{% \prime}_{2^{-t}}$ has a cycle}]$ .

To prove Equation 5, we will index the edges in $E$ with $[n]$ , and view each $S\subseteq[n]$ as the corresponding subset $E_{S}$ of edges in $E$ . Denote by $F$ the event that the edge set $E_{S}$ induces a forest in $G$ , i.e., the subgraph $(V,E_{S})$ does not contain a cycle. Observe that if $E_{S}\in F$ , then for a uniform $\boldsymbol{y}\in\{0,1\}^{m-n}$ , the coordinates $g(\boldsymbol{y})_{S}=(\boldsymbol{y}_{u_{i}}\oplus\boldsymbol{y}_{v_{i}})_{i% \in E_{S}}$ are uniformly distributed. Using the natural correspondence between $E_{\boldsymbol{S}}$ and $\boldsymbol{G}_{1/2}$ , this clearly implies Equation 5. Therefore,

\displaystyle\Pr_{\boldsymbol{S}}[\text{$g(\boldsymbol{y})_{\boldsymbol{S}}$ % is not uniform}]\leq\Pr[\text{$\boldsymbol{G}_{1/2}$ has a cycle}]=\Pr[\text{$% \boldsymbol{G}^{\prime}_{2^{-t}}$ has a cycle}]\leq\frac{1}{k^{\frac{2t-5}{3}}}.

This concludes the proof of Theorem 23. ∎

In the full version of the paper, we show that Theorem 23 is tight.

6 A lower bound on 3-local constructions with $m=(2-\epsilon)n$

In this section we prove a lower bound on the distance for all 3-local constructions with $m=1.99n$ .

Theorem 25.

Let $n\in\mathbb{N}$ be sufficiently large. Fix $\epsilon>0$ , and let $m=(2-\epsilon)n$ . Then, for any $3$ -local mapping $f\colon\{0,1\}^{m}\to\{0,1\}^{n}$ it holds that

\mathrm{dist}\bigl(f(U_{m}),\textnormal{Ber}(1/4)^{n}\bigr)\geq n^{-O(1/% \epsilon)}.

Proof.

Let $G=(V=I\cup O,E)$ be a bipartite graph, where $|I|=m=(2-\epsilon)n$ represents the input bits of $f$ , $|O|=n$ represents the output bits, and $(i,o)\in E$ if and only if the $o$ ’th output bit of $f$ depends on the $i$ ’th input bit.

We prove Theorem 25 by finding a small set of outputs $S\subset O$ such that its neighbourhood $N(S)$ (i.e., the input bits of $S$ ) is small. Specifically, we will find a set $S\subseteq O$ of size $\lvert S\rvert=k=O(\log(n))$ such that $\lvert N(S)\rvert\leq 2k-1$ . This indeed suffices, as for the distribution $\textnormal{Ber}(1/4)^{k}$ the probability of sampling all zeros in $S$ is exactly $4^{-k}$ , while the granularity of the inputs to $S$ implies that $f$ outputs all zeros in $S$ with probability either 0 or at least $2^{-\lvert N(S)\rvert}=2\cdot 4^{-k}$ . Therefore,

\lvert\Pr[f(U_{m})_{|S}\equiv 0]-\Pr[(\textnormal{Ber}(1/4)^{n})_{|S}\equiv 0]% \rvert\geq 4^{-k}.

In order to find such set $S$ , note that the graph $G$ has $\lvert V\rvert=(3-\epsilon)n$ vertices and $\lvert E\rvert=3n$ edges. Therefore, $\lvert E\rvert=(1+\epsilon^{\prime})\lvert V\rvert$ for $\epsilon^{\prime}=\epsilon/(3-\epsilon)$ .

We use the following lemma, saying that any sufficiently dense graph contains a set of vertices $S$ that span at least $|S|+1$ edges, such that $|S|=O(\log(n))$ .

Lemma 26 (Theorem 2 in [19]).

Let $G=(V,E)$ be a multigraph with $\lvert V\rvert\geq 2$ vertices and $\lvert E\rvert=m\geq(1+\epsilon)\lvert V\rvert$ edges for some $\epsilon=\epsilon(\lvert V\rvert)\in(0,1]$ . There exists a set of vertices $S\subseteq V$ of size $|S|\leq 8\log(\lvert V\rvert)\cdot\lceil 1/\epsilon\rceil$ spanning at least $|S|+1$ edges.

Applying Lemma 26 to $G$ , we get a subset of the vertices $C\subset V$ of size $|C|\leq 8\log(\lvert V\rvert)\cdot\lceil 1/\epsilon^{\prime}\rceil$ that spans at least $|C|+1$ edges. By taking the minimal such subset $C$ , we may assume¹¹1Otherwise, if $C$ has a vertex with $\deg_{C}(v)\leq 1$ , we can remove $v$ from $C$ , and the remaining subset $C^{\prime}$ will also satisfy the property that $|C^{\prime}|\leq 8\log(\lvert V\rvert)\cdot\lceil 1/\epsilon^{\prime}\rceil$ and it spans at least $|C^{\prime}|+1$ edges. that all vertices $v\in C$ have at least two neighbours in $C$ .

The key step of the proof is summarized in the following claim.

Claim 27.

Let $G^{\prime}=(V^{\prime}=I^{\prime}\cup O^{\prime},E^{\prime})$ be the bipartite subgraph of $G$ induced by $C$ with $I^{\prime}=I\cap C$ and $O^{\prime}=O\cap C$ , and let $k=\lvert O^{\prime}\rvert$ . Then $\lvert N_{G}(O^{\prime})\rvert\leq 2k-1$ .

Proof.

Since $\lvert E^{\prime}\rvert\geq\lvert V^{\prime}\rvert+1$ , there must be at least one vertex in $G^{\prime}$ of degree $\geq 3$ . Recall that all vertices in $O^{\prime}$ have degree either 2 or 3, and denote by $t$ the number of vertices in $O^{\prime}$ of degree 3. Consider the following two cases.

$\blacksquare$

$t=0$ : Since all vertices in $O^{\prime}$ have degree 2, the set $I^{\prime}$ must have a vertex of degree $\geq 3$ in $G^{\prime}$ . Furthermore, $\lvert E^{\prime}\rvert=2\cdot\lvert O^{\prime}\rvert=2k$ , and hence by counting degrees of the vertices in $I^{\prime}$ , we have $\lvert I^{\prime}\rvert\leq k-1$ . Finally, note that each $v\in O^{\prime}$ has at most one neighbour outside $C$ , and thus $|N_{G}(O^{\prime})|\leq\lvert I^{\prime}\rvert+\lvert O^{\prime}\rvert\leq(k-1% )+k=2k-1$ .
$\blacksquare$

$t\geq 1$ : By counting the degrees of $O^{\prime}$ in $G^{\prime}$ note that $\lvert E^{\prime}\rvert=2(k-t)+3t=2k+t$ . Similarly, by counting the degrees of $I^{\prime}$ in $G^{\prime}$ , we have $|E^{\prime}|\geq 2\lvert I^{\prime}\rvert$ . Finally, there are exactly $k-t$ nodes $v\in O^{\prime}$ with one neighbour outside $C$ , and $t$ nodes $v\in O^{\prime}$ with no neighbours outside $C$ . Therefore,

$|N_{G}(O^{\prime})|\leq|I^{\prime}|+(k-t)\leq|E^{\prime}|/2+(k-t)\leq(k+t/2)+(% k-t)\leq 2k-t/2.$

Since $|N_{G}(O^{\prime})|$ is an integer and $t\geq 1$ , it follows that $|N_{G}(O^{\prime})|\leq 2k-1$ .

In both cases we showed that $|N_{G}(O^{\prime})|\leq 2k-1$ , as required. $\hfill\vartriangleleft$ Therefore, letting $S=C\cap O$ , we get a set of size $k=\lvert S\rvert\leq\lvert C\rvert\leq 8\log(\lvert V\rvert)\cdot\lceil 1/% \epsilon^{\prime}\rceil\leq 8\log(3n)\cdot 3/\epsilon$ such that $\lvert N(S)\rvert\leq 2k-1$ . By the discussion above this implies that

\mathrm{dist}\bigl(f(U),\textnormal{Ber}(1/4)^{n}\bigr)\geq\big\lvert\Pr[f(U_{% m})_{|S}\equiv 0]-\Pr[(\textnormal{Ber}(1/4)^{n})_{|S}\equiv 0]\big\rvert\geq 4% ^{-k}\geq(3n)^{-48/\epsilon}.

This completes the proof of Theorem 25. $\hfill\blacktriangleleft$

7 A $4$ -local construction with $m=1.75n$ that is $\exp(-cn)$ -close to ${\textup{{Ber}}}(1/4)^{n}$

In this section we prove that 4-local samplers can approximate the distribution $\textnormal{Ber}(1/4)^{n}$ within exponentially small distance.

Theorem 28.

Let $n\in\mathbb{N}$ be sufficiently large, and let $m=(2-1/4)n$ . Then, there exists a $4$ -local mapping $f\colon\{0,1\}^{m}\to\{0,1\}^{n}$ such that

\mathrm{dist}(f(U_{m}),\textnormal{Ber}(1/4)^{n})\leq 2^{-cn},

for some absolute constant $c>0$ .

The proof of Theorem 28 relies on the following lemma.

Lemma 29.

Let $m, n$ be parameters such that $n\leq m\leq 2n$ , and let $M\in\mathbb{F}_{2}^{n\times(m-n)}$ be a matrix such that every row of $M$ has exactly $d$ ones. Then, there exists a $(d+1)$ -local sampler $f\colon\{0,1\}^{m}\to\{0,1\}^{n}$ satisfying

\displaystyle\mathrm{dist}\bigl(f(U_{m}),\textnormal{Ber}(1/4)^{n}\bigr)\leq% \Pr_{\boldsymbol{S}\subseteq[n]}[\text{the rows of $M_{\boldsymbol{S}}$ are % linearly dependent}],

(6)

where $M_{S}$ is the submatrix of $M$ obtained by taking only the rows of $M$ with indices in $S$ .

Proof.

Define $f\colon\{0,1\}^{n}\times\{0,1\}^{m-n}$ by $f(x,y)=x\wedge_{n}My$ . Clearly, $f$ is $(d+1)$ -local. By Claim 7, for a uniform subset $\boldsymbol{S}\subseteq[n]$ ,

	$\displaystyle\mathrm{dist}\bigl(\boldsymbol{x}\wedge_{n}(M\boldsymbol{y}),% \textnormal{Ber}(1/4)^{n}\bigr)$	$\displaystyle\leq\Pr\bigl[\text{$M\boldsymbol{y}$ is not uniform on $\{0,1\}^{% \boldsymbol{S}}$}\bigr]$
		$\displaystyle=\Pr\bigl[\text{$M_{\boldsymbol{S}}$ is linear dependent}\bigr].$

$\hfill\blacktriangleleft$

Next we state a result about the existence of a sparse matrix which satisfies the conditions in Lemma 29. We show the existence of such matrix by adapting Gallager’s result on random sparse matrices [18]. Its proof can be found in the full version of this paper.

Theorem 30.

For a sufficiently large $n\in\mathbb{N}$ there exists a matrix $M\in\mathbb{F}_{2}^{n\times 0.75n}$ with exactly 3 ones in every row and 4 ones in each column such that for a uniform subset $\boldsymbol{S}\subseteq[n]$ ,

\Pr[\text{$M_{\boldsymbol{S}}$ is linearly dependent}]\leq 2^{-0.05n}.

Theorem 28 immediately follows from applying Lemma 29 to Theorem 30.

Proof of Theorem 28.

Let $M\in\mathbb{F}_{2}^{n\times 0.75n}$ be the matrix from Theorem 30, which has 3 ones in each row. By Lemma 29, there is a 4-local sampler $f\colon\{0,1\}^{1.75n}\to\{0,1\}^{n}$ such that $\mathrm{dist}(f(U_{m}),\textnormal{Ber}(1/4)^{n})\leq\Pr[\text{$M_{\boldsymbol% {S}}$ is linear dependent}]\leq 2^{-0.05n}$ . $\hfill\blacktriangleleft$

References

[1] Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov. Sampling permutations with cell probes is hard. In 58th Annual Symposium on Theory of Computing (STOC), 2026.
[2] László Babai. Random oracles separate ${\rm PSPACE}$ from the polynomial-time hierarchy. Inform. Process. Lett., 26(1):51–53, 1987. doi:10.1016/0020-0190(87)90036-6.
[3] R. C. Baker, G. Harman, and J. Pintz. The difference between consecutive primes. II. Proc. London Math. Soc. (3), 83(3):532–562, 2001. doi:10.1112/plms/83.3.532.
[4] Chris Beck, Russell Impagliazzo, and Shachar Lovett. Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits. In 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 101–110, 2012. doi:10.1109/FOCS.2012.82.
[5] Itai Benjamini, Gil Cohen, and Igor Shinkar. Bi-lipschitz bijection between the boolean cube and the hamming ball. Israel J. Math., 212(2):677–703, 2016. doi:10.1007/s11856-016-1302-0.
[6] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4):506–519, 2003. doi:10.1145/792538.792543.
[7] Lucas Boczkowski and Igor Shinkar. On mappings on the hypercube with small average stretch. Combin. Probab. Comput., 32(2):334–348, 2023. doi:10.1017/s0963548322000281.
[8] R. B. Boppana and J. C. Lagarias. One-way functions and circuit complexity. Inform. and Comput., 74(3):226–240, 1987. doi:10.1016/0890-5401(87)90022-8.
[9] Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman. The space complexity of sampling. In 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 40:1–40:23, 2022. doi:10.4230/LIPIcs.ITCS.2022.40.
[10] Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. Ann. of Math. (2), 189(3):653–705, 2019. doi:10.4007/annals.2019.189.3.1.
[11] Gil Cohen and Leonard J. Schulman. Extractors for near logarithmic min-entropy. In 57rd Annual Symposium on Foundations of Computer Science (FOCS), pages 178–187, 2016. doi:10.1109/FOCS.2016.27.
[12] Thomas M. Cover and Joy A. Thomas. Elements of information theory. John Wiley & Sons, Inc., New York, 1991. doi:10.1002/0471200611.
[13] Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola. Pseudorandomness, symmetry, smoothing: I. In 39th Computational Complexity Conference (CCC), volume 300, pages 18:1–18:27, 2024. doi:10.4230/lipics.ccc.2024.18.
[14] Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola. Pseudorandomness, symmetry, smoothing: Ii, 2024. doi:10.48550/arXiv.2407.12110.
[15] Yevgeniy Dodis, Mihai Pătraşcu, and Mikkel Thorup. Changing base without losing space. In 43rd Annual Symposium on Theory of Computing (STOC), pages 593–602, 2010. doi:10.1145/1806689.1806771.
[16] Thomas L. Draper and Feras A. Saad. Efficient online random sampling via randomness recycling. In 37st Annual Symposium on Discrete Algorithms (SODA), pages 2473–2511, 2026. doi:10.1137/1.9781611978971.89.
[17] Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and certifying symmetric functions. In 27th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 36:1–36:21, 2023. doi:10.4230/lipics.approx/random.2023.36.
[18] R. G. Gallager. Low-density parity-check codes. IRE Trans., IT-8:21–28, 1962. doi:10.1109/tit.1962.1057683.
[19] Alexander Golovnev, Tom Gur, and Igor Shinkar. Derandomization of cell sampling. In 2023 Symposium on Simplicity in Algorithms (SOSA), pages 278–284, 2023. doi:10.1137/1.9781611977585.ch26.
[20] Mika Göös and Thomas Watson. A lower bound for sampling disjoint sets. ACM Trans. Comput. Theory, 12(3):20:1–20:13, 2020. doi:10.1145/3404858.
[21] Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu. Quantum advantage from sampling shallow circuits: beyond hardness of marginals. In 17th Innovations in Theoretical Computer Science Conference (ITCS), pages 73:1–73:14, 2026. doi:10.4230/lipics.itcs.2026.73.
[22] Torben Hagerup. Fast parallel generation of random permutations. In 18th International Colloquium on Automata, Languages, and Programming (ICALP), pages 405–416, 1991. doi:10.1007/3-540-54233-7_151.
[23] Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded independence plus noise fools products. SIAM J. Comput., 47(2):493–523, 2018. doi:10.1137/17M1129088.
[24] Johan Torkel Hastad. Computational Limitations of Small Depth Circuits. PhD thesis, Massachusetts Institute of Technology, 1986.
[25] Pooya Hatami and William Hoza. Paradigms for unconditional pseudorandom generators. Found. Trends Theor. Comput. Sci., 16(1-2):1–210, 2024. doi:10.1561/0400000109.
[26] Yang Hu, Jingxun Liang, Huacheng Yu, Junkai Zhang, and Renfei Zhou. Optimal static dictionary with worst-case constant query time. In 57th Annual Symposium on Theory of Computing (STOC), pages 278–289, 2025. doi:10.1145/3717823.3718278.
[27] Russell Impagliazzo and Moni Naor. Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology, 9(4):199–216, 1996. doi:10.1007/s001459900012.
[28] Daniel M. Kane, Anthony Ostuni, and Kewen Wu. Locality bounds for sampling Hamming slices. In 56th Annual Symposium on Theory of Computing (STOC), pages 1279–1286, 2024. doi:10.1145/3618260.3649670.
[29] Daniel M. Kane, Anthony Ostuni, and Kewen Wu. Locally sampleable uniform symmetric distributions. In 57th Annual Symposium on Theory of Computing (STOC), pages 1807–1816, 2025. doi:10.1145/3717823.3718243.
[30] Daniel M. Kane, Anthony Ostuni, and Kewen Wu. Symmetric distributions from shallow circuits, 2025. doi:10.48550/arXiv.2511.14127.
[31] Donald E. Knuth and Andrew C. Yao. The complexity of nonuniform random number generation. In Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976), pages 357–428. Academic Press, New York-London, 1976.
[32] Cheuk Ting Li. Channel simulation: Theory and applications to lossy compression and differential privacy. Foundations and Trends in Communications and Information Theory, 21(6):847–1106, December 2024. doi:10.1561/0100000141.
[33] Shachar Lovett and Emanuele Viola. Bounded-depth circuits cannot sample good codes. Comput. Complexity, 21(2):245–266, 2012. doi:10.1007/s00037-012-0039-3.
[34] Yossi Matias and Uzi Vishkin. Converting high probability into nearly-constant time—with applications to parallel hashing. In 23th Annual Symposium on Theory of Computing (STOC), pages 307–316, 1991. doi:10.1145/103418.103453.
[35] Arya Mazumdar, Venkat Chandar, and Gregory W. Wornell. Local recovery in data compression for general sources. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 2984–2988, 2015. doi:10.1109/ISIT.2015.7283004.
[36] Moshe Morgenstern. Existence and explicit constructions of $q+1$ regular ramanujan graphs for every prime power $q$ . J. Combin. Theory Ser. B, 62(1):44–62, 1994. doi:10.1006/jctb.1994.1054.
[37] Mihai Patrascu. Succincter. In 49th Annual Symposium on Foundations of Computer Science (FOCS), pages 305–313, 2008. doi:10.1109/FOCS.2008.83.
[38] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1–34:40, 2009. doi:10.1145/1568318.1568324.
[39] Ronen Shaltiel and Jad Silbak. Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions. In 56th Annual Symposium on Theory of Computing (STOC), pages 2028–2038, 2024. doi:10.1145/3618260.3649735.
[40] C. E. Shannon. A mathematical theory of communication. Bell System Tech. J., 27:379–423, 623–656, 1948. doi:10.1002/j.1538-7305.1948.tb01338.x.
[41] Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In 23th Annual Symposium on Theory of Computing (STOC), pages 77–82, 1987. doi:10.1145/28395.28404.
[42] Emanuele Viola. The complexity of distributions. SIAM J. Comput., 41(1):191–218, 2012. doi:10.1137/100814998.
[43] Emanuele Viola. Extractors for circuit sources. SIAM J. Comput., 43(2):655–672, 2014. doi:10.1137/11085983X.
[44] Emanuele Viola. Is nature a low-complexity sampler?, 2014. URL: https://emanueleviola.wordpress.com/2014/11/09/is-nature-a-low-complexity-sampler/.
[45] Emanuele Viola. New sampling lower bounds via the separator. In 38th Computational Complexity Conference (CCC), pages 26:1–26:23, 2023. doi:10.4230/lipics.ccc.2023.26.
[46] Emanuele Viola. 15 years of complexity of distributions, 2024. URL: https://emanueleviola.wordpress.com/2024/11/11/15-years-of-complexity-of-distributions/.
[47] Emanuele Viola, Omri Weinstein, and Huacheng Yu. How to store a random walk. In 31st Annual Symposium on Discrete Algorithms (SODA), pages 426–445, 2020. doi:10.5555/3381089.3381115.
[48] Adam Bene Watts and Natalie Parham. Unconditional quantum advantage for sampling with shallow circuits. In 17th Innovations in Theoretical Computer Science Conference (ITCS), pages 17:1–17:12, 2026. doi:10.4230/lipics.itcs.2026.17.
[49] Huacheng Yu. Nearly optimal static Las Vegas succinct dictionary. SIAM J. Comput., 51(3):STOC20–174–STOC20–249, 2022. doi:10.1137/20M1363649.
[50] Huacheng Yu and Wei Zhan. Sampling, flowers and communication. In 15th Innovations in Theoretical Computer Science Conference (ITCS), pages 100:1–100:11, 2024. doi:10.4230/lipics.itcs.2024.100.

[bib.bib1] [1] Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov. Sampling permutations with cell probes is hard. In 58th Annual Symposium on Theory of Computing (STOC), 2026.

[bib.bib2] [2] László Babai. Random oracles separate ${\rm PSPACE}$ from the polynomial-time hierarchy. Inform. Process. Lett., 26(1):51–53, 1987. doi:10.1016/0020-0190(87)90036-6.

[bib.bib3] [3] R. C. Baker, G. Harman, and J. Pintz. The difference between consecutive primes. II. Proc. London Math. Soc. (3), 83(3):532–562, 2001. doi:10.1112/plms/83.3.532.

[bib.bib4] [4] Chris Beck, Russell Impagliazzo, and Shachar Lovett. Large deviation bounds for decision trees and sampling lower bounds for AC0-circuits. In 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 101–110, 2012. doi:10.1109/FOCS.2012.82.

[bib.bib5] [5] Itai Benjamini, Gil Cohen, and Igor Shinkar. Bi-lipschitz bijection between the boolean cube and the hamming ball. Israel J. Math., 212(2):677–703, 2016. doi:10.1007/s11856-016-1302-0.

[bib.bib6] [6] Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4):506–519, 2003. doi:10.1145/792538.792543.

[bib.bib7] [7] Lucas Boczkowski and Igor Shinkar. On mappings on the hypercube with small average stretch. Combin. Probab. Comput., 32(2):334–348, 2023. doi:10.1017/s0963548322000281.

[bib.bib8] [8] R. B. Boppana and J. C. Lagarias. One-way functions and circuit complexity. Inform. and Comput., 74(3):226–240, 1987. doi:10.1016/0890-5401(87)90022-8.

[bib.bib9] [9] Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman. The space complexity of sampling. In 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 40:1–40:23, 2022. doi:10.4230/LIPIcs.ITCS.2022.40.

[bib.bib10] [10] Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. Ann. of Math. (2), 189(3):653–705, 2019. doi:10.4007/annals.2019.189.3.1.

[bib.bib11] [11] Gil Cohen and Leonard J. Schulman. Extractors for near logarithmic min-entropy. In 57rd Annual Symposium on Foundations of Computer Science (FOCS), pages 178–187, 2016. doi:10.1109/FOCS.2016.27.

[bib.bib12] [12] Thomas M. Cover and Joy A. Thomas. Elements of information theory. John Wiley & Sons, Inc., New York, 1991. doi:10.1002/0471200611.

[bib.bib13] [13] Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola. Pseudorandomness, symmetry, smoothing: I. In 39th Computational Complexity Conference (CCC), volume 300, pages 18:1–18:27, 2024. doi:10.4230/lipics.ccc.2024.18.

[bib.bib14] [14] Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola. Pseudorandomness, symmetry, smoothing: Ii, 2024. doi:10.48550/arXiv.2407.12110.

[bib.bib15] [15] Yevgeniy Dodis, Mihai Pătraşcu, and Mikkel Thorup. Changing base without losing space. In 43rd Annual Symposium on Theory of Computing (STOC), pages 593–602, 2010. doi:10.1145/1806689.1806771.

[bib.bib16] [16] Thomas L. Draper and Feras A. Saad. Efficient online random sampling via randomness recycling. In 37st Annual Symposium on Discrete Algorithms (SODA), pages 2473–2511, 2026. doi:10.1137/1.9781611978971.89.

[bib.bib17] [17] Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and certifying symmetric functions. In 27th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 36:1–36:21, 2023. doi:10.4230/lipics.approx/random.2023.36.

[bib.bib18] [18] R. G. Gallager. Low-density parity-check codes. IRE Trans., IT-8:21–28, 1962. doi:10.1109/tit.1962.1057683.

[bib.bib19] [19] Alexander Golovnev, Tom Gur, and Igor Shinkar. Derandomization of cell sampling. In 2023 Symposium on Simplicity in Algorithms (SOSA), pages 278–284, 2023. doi:10.1137/1.9781611977585.ch26.

[bib.bib20] [20] Mika Göös and Thomas Watson. A lower bound for sampling disjoint sets. ACM Trans. Comput. Theory, 12(3):20:1–20:13, 2020. doi:10.1145/3404858.

[bib.bib21] [21] Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu. Quantum advantage from sampling shallow circuits: beyond hardness of marginals. In 17th Innovations in Theoretical Computer Science Conference (ITCS), pages 73:1–73:14, 2026. doi:10.4230/lipics.itcs.2026.73.

[bib.bib22] [22] Torben Hagerup. Fast parallel generation of random permutations. In 18th International Colloquium on Automata, Languages, and Programming (ICALP), pages 405–416, 1991. doi:10.1007/3-540-54233-7_151.

[bib.bib23] [23] Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded independence plus noise fools products. SIAM J. Comput., 47(2):493–523, 2018. doi:10.1137/17M1129088.

[bib.bib24] [24] Johan Torkel Hastad. Computational Limitations of Small Depth Circuits. PhD thesis, Massachusetts Institute of Technology, 1986.

[bib.bib25] [25] Pooya Hatami and William Hoza. Paradigms for unconditional pseudorandom generators. Found. Trends Theor. Comput. Sci., 16(1-2):1–210, 2024. doi:10.1561/0400000109.

[bib.bib26] [26] Yang Hu, Jingxun Liang, Huacheng Yu, Junkai Zhang, and Renfei Zhou. Optimal static dictionary with worst-case constant query time. In 57th Annual Symposium on Theory of Computing (STOC), pages 278–289, 2025. doi:10.1145/3717823.3718278.

[bib.bib27] [27] Russell Impagliazzo and Moni Naor. Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology, 9(4):199–216, 1996. doi:10.1007/s001459900012.

[bib.bib28] [28] Daniel M. Kane, Anthony Ostuni, and Kewen Wu. Locality bounds for sampling Hamming slices. In 56th Annual Symposium on Theory of Computing (STOC), pages 1279–1286, 2024. doi:10.1145/3618260.3649670.

[bib.bib29] [29] Daniel M. Kane, Anthony Ostuni, and Kewen Wu. Locally sampleable uniform symmetric distributions. In 57th Annual Symposium on Theory of Computing (STOC), pages 1807–1816, 2025. doi:10.1145/3717823.3718243.

[bib.bib30] [30] Daniel M. Kane, Anthony Ostuni, and Kewen Wu. Symmetric distributions from shallow circuits, 2025. doi:10.48550/arXiv.2511.14127.

[bib.bib31] [31] Donald E. Knuth and Andrew C. Yao. The complexity of nonuniform random number generation. In Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976), pages 357–428. Academic Press, New York-London, 1976.

[bib.bib32] [32] Cheuk Ting Li. Channel simulation: Theory and applications to lossy compression and differential privacy. Foundations and Trends in Communications and Information Theory, 21(6):847–1106, December 2024. doi:10.1561/0100000141.

[bib.bib33] [33] Shachar Lovett and Emanuele Viola. Bounded-depth circuits cannot sample good codes. Comput. Complexity, 21(2):245–266, 2012. doi:10.1007/s00037-012-0039-3.

[bib.bib34] [34] Yossi Matias and Uzi Vishkin. Converting high probability into nearly-constant time—with applications to parallel hashing. In 23th Annual Symposium on Theory of Computing (STOC), pages 307–316, 1991. doi:10.1145/103418.103453.

[bib.bib35] [35] Arya Mazumdar, Venkat Chandar, and Gregory W. Wornell. Local recovery in data compression for general sources. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 2984–2988, 2015. doi:10.1109/ISIT.2015.7283004.

[bib.bib36] [36] Moshe Morgenstern. Existence and explicit constructions of $q+1$ regular ramanujan graphs for every prime power $q$ . J. Combin. Theory Ser. B, 62(1):44–62, 1994. doi:10.1006/jctb.1994.1054.

[bib.bib37] [37] Mihai Patrascu. Succincter. In 49th Annual Symposium on Foundations of Computer Science (FOCS), pages 305–313, 2008. doi:10.1109/FOCS.2008.83.

[bib.bib38] [38] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1–34:40, 2009. doi:10.1145/1568318.1568324.

[bib.bib39] [39] Ronen Shaltiel and Jad Silbak. Explicit codes for poly-size circuits and functions that are hard to sample on low entropy distributions. In 56th Annual Symposium on Theory of Computing (STOC), pages 2028–2038, 2024. doi:10.1145/3618260.3649735.

[bib.bib40] [40] C. E. Shannon. A mathematical theory of communication. Bell System Tech. J., 27:379–423, 623–656, 1948. doi:10.1002/j.1538-7305.1948.tb01338.x.

[bib.bib41] [41] Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In 23th Annual Symposium on Theory of Computing (STOC), pages 77–82, 1987. doi:10.1145/28395.28404.

[bib.bib42] [42] Emanuele Viola. The complexity of distributions. SIAM J. Comput., 41(1):191–218, 2012. doi:10.1137/100814998.

[bib.bib43] [43] Emanuele Viola. Extractors for circuit sources. SIAM J. Comput., 43(2):655–672, 2014. doi:10.1137/11085983X.

[bib.bib44] [44] Emanuele Viola. Is nature a low-complexity sampler?, 2014. URL: https://emanueleviola.wordpress.com/2014/11/09/is-nature-a-low-complexity-sampler/.

[bib.bib45] [45] Emanuele Viola. New sampling lower bounds via the separator. In 38th Computational Complexity Conference (CCC), pages 26:1–26:23, 2023. doi:10.4230/lipics.ccc.2023.26.

[bib.bib46] [46] Emanuele Viola. 15 years of complexity of distributions, 2024. URL: https://emanueleviola.wordpress.com/2024/11/11/15-years-of-complexity-of-distributions/.

[bib.bib47] [47] Emanuele Viola, Omri Weinstein, and Huacheng Yu. How to store a random walk. In 31st Annual Symposium on Discrete Algorithms (SODA), pages 426–445, 2020. doi:10.5555/3381089.3381115.

[bib.bib48] [48] Adam Bene Watts and Natalie Parham. Unconditional quantum advantage for sampling with shallow circuits. In 17th Innovations in Theoretical Computer Science Conference (ITCS), pages 17:1–17:12, 2026. doi:10.4230/lipics.itcs.2026.17.

[bib.bib49] [49] Huacheng Yu. Nearly optimal static Las Vegas succinct dictionary. SIAM J. Comput., 51(3):STOC20–174–STOC20–249, 2022. doi:10.1137/20M1363649.

[bib.bib50] [50] Huacheng Yu and Wei Zhan. Sampling, flowers and communication. In 15th Innovations in Theoretical Computer Science Conference (ITCS), pages 100:1–100:11, 2024. doi:10.4230/lipics.itcs.2024.100.

Local Samplers for Product Distributions

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our results

Theorem 1 (Special case of Theorem 8).

Theorem 2.

Theorem 3 (Theorem 19 and Theorem 25).

Theorem 4 (Theorem 23 and Theorem 28).

1.2 Proof overview

Overview of Theorem 1

Overview of Theorem 2

Definition 5 (Spillover representation).

Claim 6.

Proof.

Overview of Theorem 3 and Theorem 4

Claim 7.

Proof.

2 Local sampler for product distributions

Theorem 8.

Corollary 9.

Proof.

Lemma 10 ([31]).

Lemma 11.

▶ Remark 12.

Proof of Theorem 8.

3 Sampling 𝒑-biased distributions from static dictionary

Theorem 2. [Restated, see original statement.]

3.1 Changing bases

Claim 13.

Proof.

Lemma 14.

Proof.

3.2 Sampling 𝒑-biased distributions on polylog bits

Theorem 15.

Lemma 16 (Lemma 28 in [49]).

3.3 Concatenation

Lemma 17.

3.3.1 Proof of Theorem 2

Sampling the words

Sampling the spills

Lemma 18.

4 A lower bound for a 2-local construction with 𝒎=(𝟐−ϵ)⁢𝒏

Theorem 19.

Proposition 20.

Proof.

Claim 21.

Proof.

Proof of Theorem 19.

Case 1: |𝑵⁢(𝑰∗)|>𝒏/𝒅.

Case 2: |𝑵⁢(𝑰∗)|≤𝒏/𝒅.

Claim 22.

Proof.

5 A 3-local construction with 𝒎=1.99⁢𝒏 that is 𝟏/poly⁢(𝐧)-close to Ber⁢(𝟏/𝟒)𝐧

Theorem 23.

Proof of Theorem 23

Claim 24.

Proof.

6 A lower bound on 3-local constructions with 𝒎=(𝟐−ϵ)⁢𝒏

Theorem 25.

Proof.

Lemma 26 (Theorem 2 in [19]).

Claim 27.

Proof.

7 A 𝟒-local construction with 𝒎=1.75⁢𝒏 that is 𝐞𝐱𝐩⁡(−𝒄⁢𝒏)-close to Ber⁢(𝟏/𝟒)𝐧

Theorem 28.

Lemma 29.

Proof.

Theorem 30.

Proof of Theorem 28.

$\blacktriangleright$ Remark 12.

3 Sampling $𝒑$ -biased distributions from static dictionary

3.2 Sampling $𝒑$ -biased distributions on polylog bits

4 A lower bound for a 2-local construction with $m=(2-\epsilon)n$

Case 1: $\lvert N(I^{*})\rvert>n/d$ .

Case 2: $\lvert N(I^{*})\rvert\leq n/d$ .

5 A 3-local construction with $m=1.99n$ that is $1/{\textup{{poly}}}(n)$ -close to ${\textup{{Ber}}}(1/4)^{n}$

6 A lower bound on 3-local constructions with $m=(2-\epsilon)n$

7 A $4$ -local construction with $m=1.75n$ that is $\exp(-cn)$ -close to ${\textup{{Ber}}}(1/4)^{n}$