TY - GEN

T1 - On TC0, AC0, and arithmetic circuits

AU - Agrawal, M.

AU - Allender, E.

AU - Datta, S.

N1 - Publisher Copyright:
© 1997 IEEE.

PY - 1997

Y1 - 1997

N2 - Continuing a line of investigation that has studied the function classes P, we study the class of functions AC0. One way to define AC0 is as the class of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fanin addition and multiplication gates. In contrast to the preceding function classes, for which we know no nontrivial lower bounds, lower bounds for AC0 follow easily from established circuit lower bounds. One of our main results is a characterization of TC0 in terms of AC0: A language A is in TC0 if and only if there is a AC0 function f and a number k such that x∈AhArr/f(x)=2/sup |x|k/. Using the naming conventions, this yields: TC0=PAC0=C=AC0. Another restatement of this characterization is that TC0 can be simulated by constant-depth arithmetic circuits, with a single threshold gate. We hope that perhaps this characterization of TC0 in terms of AC0 circuits might provide a new avenue of attack for proving lower bounds. Our characterization differs markedly from earlier characterizations of TC0 in terms of arithmetic circuits over finite fields. Using our model of arithmetic circuits, computation over finite fields yields ACC0. We also prove a number of closure properties and normal forms for AC0.

AB - Continuing a line of investigation that has studied the function classes P, we study the class of functions AC0. One way to define AC0 is as the class of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fanin addition and multiplication gates. In contrast to the preceding function classes, for which we know no nontrivial lower bounds, lower bounds for AC0 follow easily from established circuit lower bounds. One of our main results is a characterization of TC0 in terms of AC0: A language A is in TC0 if and only if there is a AC0 function f and a number k such that x∈AhArr/f(x)=2/sup |x|k/. Using the naming conventions, this yields: TC0=PAC0=C=AC0. Another restatement of this characterization is that TC0 can be simulated by constant-depth arithmetic circuits, with a single threshold gate. We hope that perhaps this characterization of TC0 in terms of AC0 circuits might provide a new avenue of attack for proving lower bounds. Our characterization differs markedly from earlier characterizations of TC0 in terms of arithmetic circuits over finite fields. Using our model of arithmetic circuits, computation over finite fields yields ACC0. We also prove a number of closure properties and normal forms for AC0.

UR - http://www.scopus.com/inward/record.url?scp=78649883139&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78649883139&partnerID=8YFLogxK

U2 - 10.1109/CCC.1997.612309

DO - 10.1109/CCC.1997.612309

M3 - Conference contribution

AN - SCOPUS:78649883139

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 134

EP - 148

BT - Proceedings - 12th Annual IEEE Conference on Computational Complexity, CCC 1997 (Formerly

PB - IEEE Computer Society

T2 - 12th Annual IEEE Conference on Computational Complexity, CCC 1997

Y2 - 24 June 1997 through 27 June 1997

ER -