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

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.

If a is composite, should factorization of a be given or is factoring a in ACC?

$a$ is a constant, so factoring it is free.

In the proof given, it was a constant, but in the first problem posed, it was not, so J’s question makes sense.

In the original problem a is not a constant and the case of a prime is only given. So is there a way to find Legendre symbol for composite a in ACC assuming Legendre symbol for prime a is in ACC?

This is very nice. But the fact that computing $p \mod a$ is in ACC when $p$ is given in binary and $a$ is a constant requires an argument (right?). First look at powers of two: the quantity $2^i \mod a$ depends only on $i \mod a$, but the important point is that there are at most $\log_2 p$ (= length of the input) relevant $i$’s to consider: the bit positions of $p$. Thus we can hardwire all those and add the ones selected by the binary representation of $p$ with one $\mod a$ gate.

not an expert on this so am wondering, is this a new result or did someone already prove this? what do you think is a great ref on ACC? it seems very striking that majority is not known to be inside or outside ACC. any further discussion/survey of that in a paper etc?

vznvzn

I am not sure. Also there are many nice structural theorems on ACC. I can look them up later. But not much on what cannot be done. There are weak results on restricted subfamilies of ACC.

I agree. It seems that ACC and majority function is beyond paywall, Can you give a link to oen access review related to topic. Thanks.

With Duke losing in the first round, maybe (the) ACC isn’t so powerful after all.😉

Yes, a shocker even by “madness” standards, and the only reason I haven’t updated the post yet is that right now #14 Lafayette-LA is battling #3 Creighton evenly with 5 minutes left.