License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.26
URN: urn:nbn:de:0030-drops-182967
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18296/
Go to the corresponding LIPIcs Volume Portal

Viola, Emanuele

New Sampling Lower Bounds via the Separator

pdf-format:
LIPIcs-CCC-2023-26.pdf (0.8 MB)

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 Rank, thereby unifying sampling and data-structure lower bounds.

BibTeX - Entry

@InProceedings{viola:LIPIcs.CCC.2023.26,
  author =	{Viola, Emanuele},
  title =	{{New Sampling Lower Bounds via the Separator}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{26:1--26:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18296},
  URN =		{urn:nbn:de:0030-drops-182967},
  doi =		{10.4230/LIPIcs.CCC.2023.26},
  annote =	{Keywords: Sampling, data structures, lower bounds, cell probe, decision forest, AC0, rank, predecessor}
}

Keywords: Sampling, data structures, lower bounds, cell probe, decision forest, AC0, rank, predecessor
Collection: 38th Computational Complexity Conference (CCC 2023)
Issue Date: 2023
Date of publication: 10.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI