Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR21-073 | 24th December 2021 13:08

New sampling lower bounds via the separator

RSS-Feed




Revision #2
Authors: Emanuele Viola
Accepted on: 24th December 2021 13:08
Downloads: 33
Keywords: 


Abstract:

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.



Changes to previous version:

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


Revision #1 to TR21-073 | 5th November 2021 11:29

New sampling lower bounds via the separator





Revision #1
Authors: Emanuele Viola
Accepted on: 5th November 2021 11:29
Downloads: 85
Keywords: 


Abstract:

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.



Changes to previous version:

Typos, details, and introduction.


Paper:

TR21-073 | 3rd June 2021 17:14

Lower bounds for samplers and data structures via the cell-probe separator





TR21-073
Authors: Emanuele Viola
Publication: 3rd June 2021 17:15
Downloads: 303
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint