Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR99-012 | 19th April 1999 00:00

Bounded Depth Arithmetic Circuits: Counting and Closure



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 TC^0 (where essentially no lower bounds
are known). In this paper, we resolve several questions regarding
the closure properties of #AC^0 and GapAC^0.

Counting classes are usually characterized in terms of problems of
counting paths in a class of graphs (simple paths in directed or
undirected graphs for #P, simple paths in directed acyclic graphs
for #L, or paths in bounded-width graphs for GapNC^1). It was
shown in [BLMS98] that complete problems for depth k Boolean
AC^0 can be obtained by considering the reachability problem for
width $k$ grid graphs. It would be tempting to conjecture that
#AC^0 could be characterized by counting paths in bounded-width
grid graphs. We disprove this, but nonetheless succeed in
characterizing #AC^0 by counting paths in another family of
bounded-width graphs.


Comment #1 to TR99-012 | 20th August 2010 13:41

Theorem 16: a flaw and a fix

Comment #1
Authors: Meena Mahajan, Nitin Saurabh, Karteek Sreenivasaiah
Accepted on: 20th August 2010 13:41
Downloads: 785


Counting paths mod 5 in width 2 planar branching programs is hard for Boolean NC$^1$. We observe a flaw in the stated proof and fix it.

ISSN 1433-8092 | Imprint