|Abstract of Paper|
Arithmetic Constant-Depth Circuit Complexity Classes
by Hubie Chen
The boolean circuit complexity classes $AC^0 \subseteq AC^0[m] \subseteq TC^0 \subseteq NC^1$ have been studied intensely. Other than $NC^1$, they are defined by constant-depth circuits of polynomial size and unbounded fan-in over some set of allowed gates. One reason for interest in these classes is that they contain the boundary marking the limits of current lower bound technology: such technology exists for $AC^0$ and some of the classes $AC^0[m]$, while the other classes $AC^0[m]$ as well as $TC^0$ lack such technology. Continuing a line of research originating from Valiant's work on the counting class $\#P$, the arithmetic circuit complexity classes $\#AC^0$ and $\#NC^1$ have recently been studied. In this paper, we define and investigate the classes $\#AC^0[m]$ and $\#TC^0$. Just as the boolean classes $AC^0[m]$ and $TC^0$ give a refined view of $NC^1$, our new arithmetic classes, which fall into the inclusion chain $\#AC^0 \subseteq \#AC^0[m] \subseteq \#TC^0 \subseteq \#NC^1$, refine $\#NC^1$. These new classes (along with $\#AC^0$) are also defined by constant-depth circuits, but the allowed gates compute arithmetic functions. We also introduce the classes $DiffAC^0[m]$ (differences of two $AC^0[m]$ functions), which generalize the class $DiffAC^0$ studied in previous work.