License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
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


Tell, Roei

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

pdf-format:
LIPIcs-STACS-2018-58.pdf (0.5 MB)


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},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8500},
  URN =		{urn:nbn:de:0030-drops-85005},
  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


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