2026-07-22T12:15:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18296 2024-03-06T11:01:32Z ddc:004 open_access

New Sampling Lower Bounds via the Separator Viola, Emanuele Sampling data structures lower bounds cell probe decision forest AC0 rank predecessor 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emanuele Viola 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.26 urn:nbn:de:0030-drops-182967 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.26 eng https://creativecommons.org/licenses/by/4.0/legalcode