DIMACS Discrete Math/Theory of Computing Seminar


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


Eric Allender
Rutgers University


DIMACS Center, CoRE Building, Seminar Room 431
Rutgers University


4:30 PM
Tuesday, December 3, 1996

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