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