Constant-depth arithmetic circuits have been defined and studied in [AAD97,ABL98]; these circuits yield the function classes #AC^0 and GapAC^0. These function classes in turn provide new characterizations of the computational power of threshold circuits, and provide a link between the circuit classes AC^0 (where many lower bounds are known) and ... more >>>

Continuing the study of the relationship between $TC^0$, $AC^0$ and arithmetic circuits, started by Agrawal et al. (IEEE Conference on Computational Complexity'97), we answer a few questions left open in this paper. Our main result is that the classes Diff$AC^0$ and Gap$AC^0$ coincide, under poly-time, log-space, or log-time uniformity. From ... more >>>