When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.58
URN: urn:nbn:de:0030-drops-85005
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8500/
 Go to the corresponding LIPIcs Volume Portal

Lower Bounds on Black-Box Reductions of Hitting to Density Estimation

 pdf-format:

Abstract

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.

BibTeX - Entry

@InProceedings{tell:LIPIcs:2018:8500,
author =	{Roei Tell},
title =	{{Lower Bounds on Black-Box Reductions of Hitting to Density Estimation}},
booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages =	{58:1--58:13},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-062-0},
ISSN =	{1868-8969},
year =	{2018},
volume =	{96},
editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},