Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-073 | 3rd June 2021 17:14

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

RSS-Feed




TR21-073
Authors: Emanuele Viola
Publication: 3rd June 2021 17:15
Downloads: 190
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