Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Counting Circuits:
TR98-020 | 10th April 1998
Andris Ambainis, David Mix Barrington, Huong LeThanh

On Counting $AC^0$ Circuits with Negative Constants

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

TR99-012 | 19th April 1999
Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

Bounded Depth Arithmetic Circuits: Counting and Closure

Comments: 1

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

ISSN 1433-8092 | Imprint