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\left(\log n\right)$ "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$\left(n\right)$-degree randomized polynomial for any "$A{C}^0$" circuit.

Definition: A circuit is in "$A{C}^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$\left(n\right)$-degree randomized polynomial. Hence we get a rare circuit lower bound: this $f$ cannot be computed in $A{C}^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.