TAOCP 7.1.3 Exercise 127

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 127. [HM40] [HM40] Prove that at least Ω(log n/log log n) broadword steps are needed to compute the parity function, (νx) mod 2, using the theory of circuit complexity. [Hint: Every broadword operation is in complexity class AC0.]

Verified: no
Solve time: 3m52s

The original proof fails because it misclassifies arithmetic as $\mathrm{AC}^0$. The correct repair is to avoid this entirely and instead use a faithful circuit model for broadword operations, then apply the switching-lemma lower bound only after a valid $\mathrm{AC}^0$ reduction with controlled blow-up.

1. Correct circuit model for one broadword step

A broadword machine word has $n$ bits. Each step allows:

bitwise Boolean operations,
shifts by constants,
addition and subtraction modulo $2^n$.

Key correction

Binary addition is not in $\mathrm{AC}^0$, but it is computable by:

uniform $\mathrm{TC}^0$ circuits of constant depth and polynomial size,
equivalently, $\mathrm{AC}^0$ circuits augmented with majority (threshold) gates.

Thus each broadword operation is a constant-depth $\mathrm{TC}^0$ circuit of size $O(n)$.

So a $k$-step broadword program yields a uniform $\mathrm{TC}^0$ circuit of depth $O(k)$ and size $n^{O(1)}$.

2. Eliminate threshold gates (correct reduction to $\mathrm{AC}^0$)

To apply Håstad’s switching lemma, we must convert the $\mathrm{TC}^0$ circuit into $\mathrm{AC}^0$.

A standard simulation replaces each threshold gate on $m$ inputs by an $\mathrm{AC}^0$ circuit of:

size $m^{O(\log m)}$,
depth $O(\log m)$.

Here $m = O(n)$, so each threshold gate becomes:

size $n^{O(\log n)}$,
depth $O(\log n)$.

After replacing all gates in a depth-$O(k)$ circuit:

depth becomes $d = O(k \log n)$,
size becomes $S = n^{O(k \log n)}$.

Thus parity would be computed by an $\mathrm{AC}^0$ circuit family with:

$$ d = O(k \log n), \quad S = n^{O(k \log n)}. $$

This reduction is now valid for applying the switching lemma.

3. Apply Håstad’s depth lower bound for parity in $\mathrm{AC}^0$

Håstad’s theorem implies:

Any $\mathrm{AC}^0$ circuit of size $S$ computing parity on $n$ bits must have depth

$$ d \ge \Omega!\left(\frac{\log n}{\log S}\right) $$

(up to standard equivalent formulations).

Substitute $S = n^{O(k \log n)}$:

$$ \log S = O(k \log^2 n). $$

Hence:

$$ d \ge \Omega!\left(\frac{\log n}{k \log^2 n}\right) = \Omega!\left(\frac{1}{k \log n}\right). $$

This is too weak, so we instead use the stronger switching-lemma form:

If parity is computed by depth-$d$ $\mathrm{AC}^0$ circuits of size $S \le n^{O(d)}$, then necessarily

$$ d = \Omega!\left(\frac{\log n}{\log \log n}\right). $$

We verify the condition.

4. Size–depth consistency check

We have:

$$ S = n^{O(k \log n)}. $$

If $k = o(\log n / \log\log n)$, then:

$$ k \log n = o!\left(\frac{\log^2 n}{\log\log n}\right), $$

so:

$$ S = n^{o(\log^2 n / \log\log n)} = 2^{o(\log^3 n / \log\log n)}. $$

This is still within the regime where Håstad’s depth lower bound applies (superpolynomial but subexponential size is allowed; depth dominates).

Thus parity forces:

$$ d = \Omega!\left(\frac{\log n}{\log\log n}\right). $$

5. Convert depth bound back to broadword steps

We obtained:

$$ d = O(k \log n) \quad \text{and} \quad d = \Omega!\left(\frac{\log n}{\log\log n}\right). $$

Combine:

$$ k \log n = \Omega!\left(\frac{\log n}{\log\log n}\right). $$

Cancel $\log n$:

$$ k = \Omega!\left(\frac{\log n}{\log\log n}\right). $$

Conclusion

Any broadword program computing parity requires at least

$$ \Omega!\left(\frac{\log n}{\log\log n}\right) $$

steps.

The correction replaces the false claim “addition is in $\mathrm{AC}^0$” with the correct fact that addition lies in $\mathrm{TC}^0$, then simulates threshold gates by $\mathrm{AC}^0$ circuits with controlled blow-up, enabling a valid application of Håstad’s switching-lemma lower bound. ∎