# DIMACS Discrete Math/Theory of Computing Seminar

## Title:

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

## Speaker:

- Eric Allender
- Rutgers University

## Place:

- DIMACS Center, CoRE Building, Seminar Room 431
- Rutgers University

## Time:

- 4:30 PM
- Tuesday, December 3, 1996

Abstract:
This talk presents a new connection between the complexity classes AC^0
and TC^0. Arithmetic circuits provide the means for presenting this
relation: TC^0 corresponds in a precise way (actually -- in several precise
ways) to arithmetic AC^0 circuits.

AC^0 is a well-studied class. We know lots of things that AC^0 circuits
cannot compute (PARITY, MAJORITY, etc).
TC^0 is also a well-studied class. TC^0 characterizes the complexity of
important problems such as multiplication, division, sorting and many other
problems. We have NO good lower bounds for TC^0. It is hoped that the
material presented in this talk may lead to lower bounds for TC^0, by
providing a bridge between a well-understood domain and a domain that
is not understood at all.

You may already be familiar with the complexity classes #P, PP, and C=P.
You are somewhat less-likely to be familiar with the complexity classes
#L, PL, and C=L. Recent work also considered #NC^1, PNC^1, and C=NC^1.
You see the pattern. This talk considers #AC^0, PAC^0, and C=AC^0.
The main result is

TC^0 = PAC^0 = C=AC^0
(One interpretation of this result is that any function computed by a
threshold circuit can be computed by a constant-depth arithmetic circuit
augmented with a single threshold gate.)

The talk will also present
* Lower bounds for #AC^0
* Normal forms and closure properties
* Tempting open questions

(Joint work with Manindra Agrawal and Samir Datta)

Document last modified on November 27, 1996