Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-050 | 31st March 2016 11:41

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


Authors: Roei Tell
Publication: 31st March 2016 11:58
Downloads: 314


We consider the following problem. A deterministic algorithm tries to find a string in an unknown set $S\subseteq\{0,1\}^n$ that is guaranteed to have large density (e.g., $|S|\ge2^{n-1}$). However, 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$, where the estimates are up to a relative error of $\mu>0$. This problem is especially appealing as a derandomization problem, when $S$ is the set of satisfying assignments for a circuit that accepts many assignments.

If the error $\mu$ is sufficiently small (i.e., $\mu=O(1/n)$), then an algorithm can find an $n$-bit solution using $n$ iterative estimations, via the classical method of conditional probabilities. Our first question is whether the problem can be solved faster ``in parallel''. That is, assume that the algorithm works in iterations, where in each iteration it obtains estimates of the density of $S$ in $p=p(n)$ sets, in parallel. For this setting, we show a lower bound of $\Omega\left(\frac{n}{\log(p)+\log(1/\mu)}\right)$ iterations, which holds even when $S$ is very dense, and is tight for natural settings of the parameters. Our second question is what happens when the estimation error $\mu$ is too large to use the method of conditional probabilities. For this setting, we show that if the error satisfies $\mu=\omega(n/\log(n))$, then $2^{\Theta(\mu\cdot n)}$ estimations are both necessary and sufficient to solve the problem, regardless of parallelism.

Our results extend the results of Karp, Upfal, and Wigderson (1988), who studied the setting in which the algorithm can only probe subsets for the existence of a solution in them. Our lower bound on parallel algorithms also affirms a weak version of a conjecture of Motwani, Naor, and Naor (1994).

ISSN 1433-8092 | Imprint