Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1007/3-540-48523-6_12 | international colloquium on automata, languages and programming |
Keywords | Field | DocType |
bounded depth arithmetic circuits,function class,closure property,new characterization,constant-depth arithmetic circuit,bounded-width graph,threshold circuit,computational power,circuit classes ac0,lower bound,directed acyclic graph | Discrete mathematics,Arithmetic circuits,Combinatorics,Closure problem,Directed acyclic graph,Arithmetic circuit complexity,Saturation arithmetic,Directed acyclic word graph,Mathematics,Bounded function | Journal |
Volume | Issue | ISBN |
6 | 12 | 3-540-66224-3 |
Citations | PageRank | References |
15 | 0.89 | 22 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eric Allender | 1 | 1434 | 121.38 |
| Andris Ambainis | 2 | 2000 | 183.24 |
| David A. Mix Barrington | 3 | 856 | 94.79 |
| Samir Datta | 4 | 200 | 19.82 |
| Huong LeThanh | 5 | 52 | 3.38 |
| gapac | 6 | 15 | 0.89 |