2026-07-23T16:54:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8500 2024-03-06T10:42:23Z ddc:004 open_access

Lower Bounds on Black-Box Reductions of Hitting to Density Estimation Tell, Roei Approximate Counting Lower Bounds Derandomization Parallel Algorithms Query Complexity Consider a deterministic algorithm that tries to find a string in an unknown set S\subseteq{0,1}^n, under the promise that S has large density. The only information that the algorithm can obtain about S is estimates of the density of S in adaptively chosen subsets of {0,1}^n, up to an additive error of mu>0. This problem is appealing as a derandomization problem, when S is the set of satisfying inputs for a circuit C:{0,1}^n->{0,1} that accepts many inputs: In this context, an algorithm as above constitutes a deterministic black-box reduction of the problem of hitting C (i.e., finding a satisfying input for C) to the problem of approximately counting the number of satisfying inputs for C on subsets of {0,1}^n. We prove tight lower bounds for this problem, demonstrating that naive approaches to solve the problem cannot be improved upon, in general. First, we show a tight trade-off between the estimation error mu and the required number of queries to solve the problem: When mu=O(log(n)/n) a polynomial number of queries suffices, and when mu>=(4log(n)/n) the required number of queries is 2^{Theta(mu \cdot n)}. Secondly, we show that the problem "resists" parallelization: Any algorithm that works in iterations, and can obtain p=p(n) density estimates "in parallel" in each iteration, still requires Omega( frac{n}{log(p)+log(1/mu)} ) iterations to solve the problem. This work extends the well-known work of Karp, Upfal, and Wigderson (1988), who studied the setting in which S is only guaranteed to be non-empty (rather than dense), and the algorithm can only probe subsets for the existence of a solution in them. In addition, our lower bound on parallel algorithms affirms a weak version of a conjecture of Motwani, Naor, and Naor (1994); we also make progress on a stronger version of their conjecture. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Roei Tell 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.58 urn:nbn:de:0030-drops-85005 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.58 eng https://creativecommons.org/licenses/by/3.0/legalcode