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:\bitset^n\ra\bitset$ 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 $\bitset^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\ge4\cdot(\log(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\left(\frac{n}{\log(p)+\log(1/\mu)}\right)$ 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.
A few minor fixes, a significantly revised exposition, and an explicit statement of a theorem that was previously implicit (Thm 4).
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).
