Name
Abstract | ||
|---|---|---|
A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs – polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known that width-3 PBPs require exponential size to compute the AND function. No such lower bound is known for width-4 PBPs, however it is widely conjectured that width-4 PBPs will not capture all of NC1. In this work, we study the power of bounded width branching programs by comparing them with bounded width skew circuits. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.tcs.2017.03.013 | Theoretical Computer Science |
Keywords | DocType | Volume |
Branching programs,Barrington's theorem,Skew circuits,Lower bounds,Parity | Journal | 821 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikhil Balaji | 1 | 9 | 4.24 |
| Andreas Krebs | 2 | 17 | 2.86 |
| Nutan Limaye | 3 | 134 | 20.59 |