Name
Abstract | ||
|---|---|---|
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a π2 MOD C0 circuit can also be computed by a constant width polynomial size cylindrical nondeterministic branching program (or cylindrical circuit) and that every function computed by a constant width polynomial size cylindrical circuit belongs to ACC0. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/s.00037-006-0207-4 | Computational Complexity |
Keywords | Field | DocType |
constant width polynomial size,branching programs. subject classification. 68q05,68q70.,cylindrical circuit,. circuit complexity,mod c0 circuit,computational power,cylindrical nondeterministic,branching program,circuit complexity | Boolean function,Discrete mathematics,Combinatorics,Cylinder (engine),Nondeterministic algorithm,Polynomial,Circuit complexity,Cylinder,ACC0,Electronic circuit,Mathematics | Journal |
Volume | Issue | ISSN |
15 | 1 | 1420-8954 |
Citations | PageRank | References |
3 | 0.40 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kristoffer Arnsfelt Hansen | 1 | 176 | 21.40 |
| Peter Bro Miltersen | 2 | 1146 | 94.49 |
| V. Vinay | 3 | 401 | 67.84 |