Andris Ambainis, David Mix Barrington, Huong LeThanh

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$ ...
more >>>

Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

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 ...
more >>>