# 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. ...

Publication status:
Published
Peer review status:
Peer reviewed

### Access Document

Files:
• (Accepted manuscript, pdf, 367.3KB)
Publisher copy:
10.1016/j.tcs.2017.03.013

### Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
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
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