Journal article
Skew circuits of small width
- 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. ...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Accepted manuscript, pdf, 367.3KB)
-
- Publisher copy:
- 10.1016/j.tcs.2017.03.013
Authors
Bibliographic Details
- Publisher:
- Elsevier Publisher's website
- Journal:
- Theoretical Computer Science Journal website
- Volume:
- 831
- Pages:
- 111-123
- Publication date:
- 2017-03-21
- Acceptance date:
- 2017-03-16
- DOI:
- ISSN:
-
0304-3975
Item Description
- Language:
- English
- Keywords:
- Pubs id:
-
pubs:1013441
- UUID:
-
uuid:8eae127f-8bde-41f3-a1ec-bebe2f154d8d
- Local pid:
- pubs:1013441
- Source identifiers:
-
1013441
- Deposit date:
- 2019-06-14
Terms of use
- Copyright holder:
- Elsevier BV
- Copyright date:
- 2017
- Rights statement:
- © 2017 Elsevier B.V. All rights reserved.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Elsevier at: https://doi.org/10.1016/j.tcs.2017.03.013
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record