Suppose that a distribution $S$ can be approximately sampled by an

efficient cell-probe algorithm. It is shown to be possible to restrict

the input to the algorithm so that its output distribution is still

not too far from $S$, and at the same time many output coordinates

are almost pairwise independent.

Building on this several results are obtained, including:

- A lower bound for sampling prefix sums.

- A lower bound for sampling a variant of the predecessor problem.

- A separation between AC0 and cell-probe sampling.

- A separation between sampling with $O(q)$ and $q$ probes.

- A new proof of the Patrascu-Viola data-structure lower bound for

prefix sums, demonstrating the feasibility of obtaining data-structure

lower bounds via sampling.

- A separation between data structures making $O(q)$ and $q$ probes.

The only previous cell-probe lower bounds for sampling followed from

the AC0 lower bounds and applied to pseudorandom objects like error-correcting

and extractors, making them inadequate for the above applications.

Suppose that a target distribution can be approximately sampled by a low-depth decision tree, or more generally by an efficient cell-probe algorithm. It is shown to be possible to restrict the input to the sampler so that its output distribution is still not too far from the target distribution, and at the same time many output coordinates are almost pairwise independent.

This new tool is then used to obtain several new sampling lower bounds and separations, including a separation between AC0 and low-depth decision trees, and a hierarchy theorem for sampling. It is also used to obtain a new proof of the Patrascu-Viola data-structure lower bound for prefix sums, thereby unifying sampling and data-structure lower bounds.

Made explicit a Markov-inequality step in the proof of Lemma 17, and reworded other bits of the proof.

Suppose that a target distribution can be approximately sampled by a low-depth decision tree, or more generally by an efficient cell-probe algorithm. It is shown to be possible to restrict the input to the sampler so that its output distribution is still not too far from the target distribution, and at the same time many output coordinates are almost pairwise independent.

This new tool is then used to obtain several new sampling lower bounds and separations, including a separation between AC0 and low-depth decision trees, and a hierarchy theorem for sampling. It is also used to obtain a new proof of the Patrascu-Viola data-structure lower bound for prefix sums, thereby unifying sampling and data-structure lower bounds.

Typos, details, and introduction.

Suppose that a distribution $S$ can be approximately sampled by an

efficient cell-probe algorithm. It is shown to be possible to restrict

the input to the algorithm so that its output distribution is still

not too far from $S$, and at the same time many output coordinates

are almost pairwise independent.

Building on this several results are obtained, including:

- A lower bound for sampling prefix sums.

- A lower bound for sampling a variant of the predecessor problem.

- A separation between AC0 and cell-probe sampling.

- A separation between sampling with $O(q)$ and $q$ probes.

- A new proof of the Patrascu-Viola data-structure lower bound for

prefix sums, demonstrating the feasibility of obtaining data-structure

lower bounds via sampling.

- A separation between data structures making $O(q)$ and $q$ probes.

The only previous cell-probe lower bounds for sampling followed from

the AC0 lower bounds and applied to pseudorandom objects like error-correcting

and extractors, making them inadequate for the above applications.