Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-073 | 3rd June 2021 17:14

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


Authors: Emanuele Viola
Publication: 3rd June 2021 17:15
Downloads: 190


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