## DIMACS TR: 97-48

## On TC^0, AC^0, and Arithmetic Circuits

### Authors: Manindra Agrawal,
Eric Allender and
Samir Datta

**
ABSTRACT
**

Continuing a line of investigation that has studied the function classes
#P, #SAC^1, #L, and #NC^1, we study the class of functions #AC^0. One
way to define #AC^0 is as the class of functions computed by constant-depth
polynomial-size arithmetic circuits of unbounded fan-in addition and
multiplication gates. In contrast to the preceding function classes, for
which we know no nontrivial lower bounds, lower bounds for #AC^0 follow
easily from established circuit lower bounds.

One of our main results is a characterization of TC^0 in terms of
#AC^0: A language A is in TC^0 if and only if there is a #AC^0 function
f and a number k such that x is in A iff f(x) = 2^|x|^k. Using the
naming conventions of this area of research, this yields:
TC^0 = PAC^0 = C=AC^0

Another restatement of this characterization is that TC^0 can be simulated
by constant-depth arithmetic circuits, with a single threshold gate.
We hope that perhaps this characterization of TC^0 in terms of AC^0 circuits
might provide a new avenue of attack for proving lower bounds.

Our characterization differs markedly from earlier characterizations of
TC^0 in terms of arithmetic circuits over finite fields. Using our model
of arithmetic circuits, computation over finite fields yields ACC.

We also prove a number of closure properties and normal forms for #AC^0.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-48.ps.gz

DIMACS Home Page