Abstract of Paper

Arithmetic Constant-Depth Circuit Complexity Classes
by Hubie Chen

Abstract:

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.