TR99-012 Authors: Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

Publication: 20th April 1999 09:05

Downloads: 3869

Keywords:

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 Authors: Meena Mahajan, Nitin Saurabh, Karteek Sreenivasaiah

Accepted on: 20th August 2010 13:41

Downloads: 2022

Keywords:

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.