{\huge The Power Of ACC}
Euler's back-door pass to Gauss sinks a bucket
ACC stands for the Atlantic Coast Conference, which is an athletic organization that contains Georgia Tech and fourteen other colleges. In basketball, the top several teams in the ACC qualified for the NCAA championship tournament, which started today. We call the NCAA tournament ``March Madness'' because the opening rounds have games being shown on national TV seemingly every hour of every day, and often some spectacular upsets happen. Indeed Harvard has just beaten a favored University of Cincinnati team. Unfortunately Tech was not among the qualifiers from the ACC, as we had a losing record this year.
Today I want talk about another ACC: our own complexity class.
Recall that ACC, as a complexity class, is the class of Boolean functions computed by boolean circuits of constant depth and polynomial size, and the gates include modular gates that can count the number of $latex {1}&fg=000000$ inputs modulo a fixed constant. This class is quite mysterious. It could be very powerful, yet we do not even know if it contains the majority function.
The Problem
Suppose you have a number $latex {a}&fg=000000$. Now I give you an $latex {n}&fg=000000$-bit prime number $latex {p}&fg=000000$ and ask that you check whether $latex {a}&fg=000000$ is a quadratic residue modulo $latex {p}&fg=000000$. Recall that means that there is a $latex {b}&fg=000000$ such that
$latex \displaystyle a \equiv b^{2} \bmod p. &fg=000000$
This is the problem we are interested in solving with an ACC circuit. Note that it is a promise problem---we only ask that your computation works when the input number $latex {p}&fg=000000$ is a prime.
An Approach
An obvious idea is to use the famous Euler criterion, which says that $latex {a}&fg=000000$ is a quadratic residue if and only if
$latex \displaystyle a^{\frac{p-1}{2}} \equiv 1 \bmod p. &fg=000000$
Thus we need only raise $latex {a}&fg=000000$ to a power by repeated squaring and so on. The trouble, of course, is that we do not know whether ACC can do the required repeated multiplication.
Another Approach
Now let's expressly state that $latex {a}&fg=000000$ is bounded in size by some constant. Still the Euler approach looks hopeless. But there is a deep theorem of number theory that comes to the rescue: quadratic reciprocity. Define the Legendre symbol
$latex \displaystyle \left( \frac{a}{p} \right) &fg=000000$
as the value $latex { a^{\frac{p-1}{2}} \bmod p}&fg=000000$ where $latex {p}&fg=000000$ is a prime. Note it is always $latex {-1,0,+1}&fg=000000$: it is only $latex {0}&fg=000000$ when $latex {p}&fg=000000$ divides $latex {a}&fg=000000$. Thus our problem is to compute$latex \displaystyle \left( \frac{a}{p} \right) &fg=000000$
for $latex {p}&fg=000000$ an input and $latex {a}&fg=000000$ bounded in size.This is in ACC. The key is we can use the deep quadratic reciprocity theorem which says that
$latex \displaystyle \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2}}(-1)^{\frac{q-1}{2}}, &fg=000000$
where $latex {p}&fg=000000$ and $latex {q}&fg=000000$ are primes. The theorem was conjectured by Leonhard Euler and Adrien-Marie Legendre, but finally proved by Carl Gauss. He referred to it as ``the fundamental theorem'' and wrote: The fundamental theorem must certainly be regarded as one of the most elegant of its type.So how do we proceed? Suppose first that the constant $latex {a}&fg=000000$ is a prime. Then we know by reciprocity that
$latex \displaystyle \left( \frac{a}{p} \right) \left( \frac{p}{a} \right) = (-1)^{\frac{a-1}{2}}(-1)^{\frac{p-1}{2}}. &fg=000000$
The right-hand side is easy to compute in ACC. To determine it we need only compute $latex {p}&fg=000000$'s residue modulo $latex {4}&fg=000000$. Since $latex {p}&fg=000000$ is given in binary this is trivial. Thus, all reduces to the computation of $latex {\left( \frac{p}{a} \right)}&fg=000000$. The key is that the Legendre symbol only depends on the value of $latex {p}&fg=000000$ modulo $latex {a}&fg=000000$. Since we can do this in ACC we are done for the case when $latex {a}&fg=000000$ is a prime.When $latex {a}&fg=000000$ is composite we use one simple fact about the Legendre symbol that follows directly from its definition.
$latex \displaystyle \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right). &fg=000000$
Thus we can use the case where $latex {a}&fg=000000$ is prime multiple times.
Open Problems
The Legendre symbol for bounded $latex {a}&fg=000000$ is thus in ACC---the complexity class, not the conference. The rationale for this discussion is two-fold. One it shows that obvious approaches to a problem may sometimes be avoided by deep mathematics. Is this possible to do the same for other problems that we care about? The permanent, for example? Another rationale is the perennially important open problem: what can ACC actually compute? It may be hard to resolve the majority function, but perhaps other functions can be shown to be in ACC. Good luck thinking about this.