Name
Abstract | ||
|---|---|---|
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 no 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 is in A iff f(x) = 2^|x|^k. Using the naming conventions of this area of research, this yields: TC^0 = PAC^0 = C=AC^0 Another restatement of this characterization is that TC^0 can be simulated by constant-depth arithmetic circuits, with a single threshold gate. We hope that perhaps this characterization of TC^0 in terms of AC^0 circuits might provide a new avenue of attack for proving lower bounds. Our characterization differs markedly from earlier characterizations of TC^0 in terms of arithmetic circuits over finite fields. Using our model of arithmetic circuits, computation over finite fields yields ACC. We also prove a number of closure properties and normal forms for #AC^0. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1006/jcss.1999.1675 | Journal of Computer and System Sciences - Eleventh annual conference on computational learning theory&slash;Twelfth Annual IEEE conference on computational complexity |
Keywords | DocType | Volume |
function class,arithmetic circuit,constant-depth arithmetic circuit,finite field,arithmetic circuits,earlier characterization,number k,preceding function class,constant-depth polynomial-size arithmetic circuit,lower bound,nontrivial lower bound | Conference | 60 |
Issue | ISSN | ISBN |
2 | 1093-0159 | 0-8186-7907-7 |
Citations | PageRank | References |
21 | 1.13 | 41 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manindra Agrawal | 1 | 581 | 45.56 |
| Eric Allender | 2 | 1434 | 121.38 |
| Samir Datta | 3 | 200 | 19.82 |