The Power Of ACC

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.

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 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.

Alas the ACC qualifiers for the men’s tournament did not contain Georgia Tech, for our men’s team had a losing record this year. Our women’s team, however, played well enough to receive an at-large entry into the NCAA Women’s championship, which is staggered two days after the men and so begins Saturday. No Buffalo team made either. The tournaments run through April 7 and 8. Go Yellow Jackets.

The Problem

Suppose you have a number . Now I give you an -bit prime number and ask that you check whether is a quadratic residue modulo . Recall that means that there is a such that

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 is a prime.

An Approach

An obvious idea is to use the famous Euler criterion, which says that is a quadratic residue if and only if

Thus we need only raise 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 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

as the value where is a prime. Note it is always : it is only when divides . Thus our problem is to compute

for an input and bounded in size.

This is in ACC. The key is we can use the deep quadratic reciprocity theorem which says that

where and 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 is a prime. Then we know by reciprocity that

The right-hand side is easy to compute in ACC. To determine it we need only compute ‘s residue modulo . Since is given in binary this is trivial. Thus, all reduces to the computation of . The key is that the Legendre symbol only depends on the value of modulo . Since we can do this in ACC we are done for the case when is a prime.

When is composite we use one simple fact about the Legendre symbol that follows directly from its definition.

Thus we can use the case where is prime multiple times.

Open Problems

The Legendre symbol for bounded 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.