ECCC-Report TR99-012https://eccc.weizmann.ac.il/report/1999/012Comments and Revisions published for TR99-012en-usFri, 20 Aug 2010 13:41:20 +0300
Comment 1
| Theorem 16: a flaw and a fix |
Meena Mahajan,
Nitin Saurabh,
Karteek Sreenivasaiah
https://eccc.weizmann.ac.il/report/1999/012#comment1Counting 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. Fri, 20 Aug 2010 13:41:20 +0300https://eccc.weizmann.ac.il/report/1999/012#comment1
Paper TR99-012
| Bounded Depth Arithmetic Circuits: Counting and Closure |
Eric Allender,
Andris Ambainis,
David Mix Barrington,
Samir Datta,
Huong LeThanh
https://eccc.weizmann.ac.il/report/1999/012Constant-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.
Tue, 20 Apr 1999 09:05:12 +0300https://eccc.weizmann.ac.il/report/1999/012