TAOCP 7.1.2 Exercise 63

We restart from the structure implicit in Exercises 62–63.

taocpmathematicsalgorithmsvolume-4hm-hard

Section 7.1.2: Boolean Evaluation

Exercise 63. [HM35] [HM35] (L. A. Sholomov, 1969.) Continuing exercise 62, prove that all such functions have cost $\le 2^n c/n(1 + O(n^{-1} \log n))$. Hint: There is a set of $2^n (1 + k)$ vectors $x_1 \ldots x_k$ that intersects every $(k - n)$-dimensional subcube of the 3-cube.

Verified: no
Solve time: 2m05s

We restart from the structure implicit in Exercises 62–63. The objects under consideration are functions on the ternary cube

$$ {0,1,2}^n, $$

and their implementation cost is proportional (with constant factor $c$) to the size of a certain covering set of vectors used to realize the function. Exercise 62 reduces the problem to constructing a small set of points that intersects all sufficiently large subcubes, and Exercise 63 asks for a sharp asymptotic bound on the size of such a construction.

Let a $d$-dimensional subcube of ${0,1,2}^n$ be obtained by choosing $d$ free coordinates and fixing the remaining $n-d$ coordinates to arbitrary values in ${0,1,2}$. Thus every $d$-subcube has exactly $3^d$ points, and the total number of $d$-subcubes is

$$ N_d = \binom{n}{d} 3^{n-d}. $$

We set $d = k-n$, as in the problem statement. The hint asserts the existence of a set $S$ of size $2^n(1+k)$ that intersects every $(k-n)$-dimensional subcube. We now construct such a set and then optimize $k$.

We use the probabilistic method. Choose $m$ points independently and uniformly from ${0,1,2}^n$, allowing repetition. Fix a particular $(k-n)$-subcube $C$. Since $|C| = 3^{k-n}$, the probability that a random point lies in $C$ is $3^{k-n}/3^n = 3^{k-2n}$. Hence the probability that none of the $m$ chosen points lies in $C$ is

$$ (1 - 3^{k-2n})^m \le \exp(-m 3^{k-2n}). $$

By the union bound over all such subcubes,

$$ \mathbb{P}(\text{some } (k-n)\text{-subcube is missed}) \le \binom{n}{k-n} 3^{n-(k-n)} \exp(-m 3^{k-2n}). $$

It suffices to choose $m$ so that this quantity is less than 1. Using Stirling’s approximation in the form

$$ \binom{n}{k-n} = \exp!\big(n H((k-n)/n) + O(\log n)\big), $$

where $H$ is the binary entropy function, and optimizing in the regime $k-n = O(\log n)$, we obtain

$$ \log \binom{n}{k-n} = O(\log n). $$

Meanwhile,

$$ 3^{n-(k-n)} = 3^{2n-k}. $$

Thus it is enough to take

$$ m = 3^{2n-k}\big(O(\log n)\big), $$

so that the exponential term dominates the polynomial number of subcubes.

Now choose $k$ to minimize