On TC0, AC0, and Arithmetic Circuits

✍ Scribed by Manindra Agrawal; Eric Allender; Samir Datta

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 262 KB
• Volume: 60
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1675

✦ Synopsis

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 to 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 # A f (x)=2 |x| k . Using the naming conventions of