Trivial lemma => powerful circuit lower bounds

Remember the very first lemma we used in the proof of the Valiant-Vazirani Theorem? Though simple, it's actually extremely useful. Here is an equivalent way to state it:

Lemma: There is a degree-2 "randomized $F_2$-polynomial" for the OR function. Precisely, the degree-2 polynomial

$p(x,r) = \sum_{i=1}^n r_i x_i$ mod 2

computes the function OR($x$) with one-sided error $1/2$ when its "random bits" $r$ are chosen uniformly.

It's an easy exercise to show from this that there is a degree-$O(\log n)$ "randomized $F_2$-polynomial" which computes the OR function with one-sided error $1/n^{100}$. Of course, there is similarly one for AND. By combining these, you can get a polylog$(n)$-degree randomized polynomial for any "$AC^0$" circuit.

Definition: A circuit is in "$AC^0$" if it is of polynomial size and constant depth. Here we allow AND and OR gates of unbounded fan-in (otherwise you couldn't even compute the AND of all bits in constant depth!).

But for some basic functions -- e.g., the function

$f(x_1, ... , x_n) = \sum_{i=1}^n x_i$ mod 3

-- it's not too hard to show that they can't have a polylog$(n)$-degree randomized polynomial. Hence we get a rare circuit lower bound: this $f$ cannot be computed in $AC^0$.

We will probably do this more explicitly later in the course. This idea is also used crucially in Braverman's remarkable paper, discussed in an earlier blog post.