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 blackbox 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 tradeoff 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 wellknown work of Karp, Upfal, and Wigderson (1988), who studied the setting in which S is only guaranteed to be nonempty (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 BlackBox Reductions of Hitting to Density Estimation}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {58:158:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8500},
URN = {urn:nbn:de:0030drops85005},
doi = {10.4230/LIPIcs.STACS.2018.58},
annote = {Keywords: Approximate Counting, Lower Bounds, Derandomization, Parallel Algorithms, Query Complexity}
}
Keywords: 

Approximate Counting, Lower Bounds, Derandomization, Parallel Algorithms, Query Complexity 
Collection: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) 
Issue Date: 

2018 
Date of publication: 

27.02.2018 