Arithmetic Constant-Depth Circuit Complexity Classes

Abstract The boolean circuit complexity classes AC 0 ⊆ AC 0 [ m ] ⊆ TC 0 ⊆ 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 \(\ensuremath{\sharp} P\), the arithmetic circuit complexity classes \(\ensuremath{\sharp} AC^0\) and \(\ensuremath{\sharp} NC^1\) have recently been studied. In this paper, we define and investigate the classes \(\ensuremath{\sharp} AC^0[m]\) and \(\ensuremath{\sharp} TC^0\), new arithmetic circuit complexity classes that are defined by constant-depth circuits and are analogues of the classes AC 0 [ m ] and TC 0.

Authors

• Hubie Chen

Keywords

No keywords are indexed for this paper.