## Abstract

Continuing a line of investigation that has studied the function classes P, 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 fanin 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∈AhArr/f(x)=2/sup |x|k/. Using the naming conventions, 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^{0}. We also prove a number of closure properties and normal forms for AC^{0}.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 12th Annual IEEE Conference on Computational Complexity, CCC 1997 (Formerly |

Subtitle of host publication | Structure in Complexity Theory Conference) |

Publisher | IEEE Computer Society |

Pages | 134-148 |

Number of pages | 15 |

ISBN (Electronic) | 0818679077 |

DOIs | |

State | Published - 1997 |

Event | 12th Annual IEEE Conference on Computational Complexity, CCC 1997 - Ulm, Germany Duration: Jun 24 1997 → Jun 27 1997 |

### Publication series

Name | Proceedings of the Annual IEEE Conference on Computational Complexity |
---|---|

ISSN (Print) | 1093-0159 |

### Other

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

Country/Territory | Germany |

City | Ulm |

Period | 6/24/97 → 6/27/97 |

## All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Computational Mathematics

## Fingerprint

Dive into the research topics of 'On TC^{0}, AC

^{0}, and arithmetic circuits'. Together they form a unique fingerprint.