Loading jsMath...
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: 3410
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 DiffAC^0 and
GapAC^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