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
(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)