Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-020 | 10th April 1998 00:00

On Counting $AC^0$ Circuits with Negative Constants

RSS-Feed




TR98-020
Authors: Andris Ambainis, David Mix Barrington, Huong LeThanh
Publication: 15th April 1998 02:48
Downloads: 3223
Keywords: 


Abstract:

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 that we can derive that under logspace
uniformity, the following equalities hold:
\[C_=AC^0=PAC^0=TC^0.\]



ISSN 1433-8092 | Imprint