The Exercise

A search problem on $N$ items is given by an oracle, a function $f$ from $\{0, \dots, N-1\}$ to $\{0, 1\}$ . The items $x$ with $f(x) = 1$ are the solutions, and $M$ is their number.^✦ A classical algorithm learns about $f$ only by calling the oracle on one item at a time, and it may choose each item from the answers it has had and from coins of its own. The exercise asks how many calls such an algorithm needs if it is to estimate $M$ to within $c\sqrt{M}$ , for a constant $c$ , with probability at least $3/4$ , and to do so for every oracle, whatever the value of $M$ . The answer is a number of calls at least proportional to $N$ , once $N$ is large compared with $c^2$ .

Counting Algorithms

The number of solutions $M(f)$ of an oracle $f$ on $N$ items is the number of items $x$ with $f(x) = 1$ : $M(f) = \bigl|\{\, x \in \{0, \dots, N-1\} : f(x) = 1 \,\}\bigr|.$ (1)^✦

A decision tree $t$ on $N$ items is either a leaf, which carries a real number $r$ , its estimate, or a node, which queries an item $i$ and has a subtree $t_0$ for the answer $0$ and a subtree $t_1$ for the answer $1$ .^✦ It is a deterministic classical algorithm. The output $t(f)$ of the tree on an oracle $f$ is $r$ if $t$ is a leaf with estimate $r$ ; if $t$ queries $i$ , it is the output of the subtree that the answer $f(i)$ selects, $t(f) = t_{f(i)}(f).$ (2)^✦ The depth of a tree is the largest number of queries on a path from its root to a leaf, the number of oracle calls it makes in the worst case.

A randomized counting algorithm $\mathcal{A}$ on $N$ items is a family of decision trees $t_\omega$ on $N$ items, indexed by the outcomes $\omega$ of a probability space $(\Omega, \mu)$ , with a budget $T$ , a natural number that bounds the depth of every tree, such that for each oracle $f$ the output $t_\omega(f)$ is a random variable on $\Omega$ .^✦ The output $\mathcal{A}(f)$ of a randomized counting algorithm $\mathcal{A}$ on an oracle $f$ is the random number obtained by drawing $\omega$ from $\mu$ and taking the output of $t_\omega$ on $f$ : $\mathcal{A}(f) = t_\omega(f), \quad \omega \sim \mu, \qquad \operatorname{depth}(t_\omega) \le T \ \text{for every } \omega \in \Omega.$ (3)

The Claim

Theorem 1. Let $c \ge 0$ . There is a constant $a > 0$ with the following property. Let $N \ge 2(\lceil c^2 \rceil + 1)$ , and let $\mathcal{A}$ be a randomized counting algorithm on $N$ items with budget $T$ whose estimate lies within $c\sqrt{M(f)}$ of $M(f)$ with probability at least $3/4$ for every oracle $f$ : $\mu\bigl(\{\, \omega \in \Omega : |t_\omega(f) - M(f)| \le c\sqrt{M(f)} \,\}\bigr) \ge \tfrac{3}{4}.$ (4)^✦ Then $T \ge aN$ .

What Is Checked

The claim is stated over the randomized counting algorithm (3), its decision trees with their output (2), and the number of solutions (1). What the library proves about these constructions is Theorem 1, for every $c \ge 0$ .