Bounded Depth Arithmetic Circuits: Counting and Closure

Constant-depth arithmetic circuits have been dened and studied in [AAD97, ABL98]; these circuits yield the function classes #AC0 and GapAC0. These function classes in turn provide new characterizations of the computational power of threshold circuits, and provide a link between the circuit classes AC0 (where many lower bounds are known) and TC0 (where essentially no lower bounds are known). In this paper, we resolve several questions regarding the closure properties of #AC0 and GapAC0. 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 GapNC1). It was shown in [BLMS98] that complete problems for depth k Boolean AC0 can be obtained by considering the reachability problem for width k grid graphs. It would be tempting to conjecture that #AC0 could be characterized by counting paths in bounded-width grid graphs. We disprove this, but nonetheless succeed in characterizing #AC0 by counting paths in another family of bounded-width graphs