On Learning Width Two Branching Programs (Extended Abstract)
Abstract
Nader H. Bshouty Christino Tamon David K. Wilson Department of Computer Science The University of Calgary 2500 University Drive NW Calgary, Alberta, Canada T2N 1N4 e-mail:fbshouty, tamon, [email protected] Abstract We prove that strict width two branching programs or SW 2 (which are width two branching programs with exactly two sinks, as defined in [BDFP86]) are properly PAC learnable under any distribution. We also observe that PAC learning monotone width two branching programs (which are width two branching programs with exactly one rejecting sink) is as hard as learning DNF formulae. This work refines both the positive and negative results in [ERR95] and answers one of the open questions in that paper. 1 Introduction Many interesting results have been found due to the study of branching programs most notably by Barrington [B89] who demonstrated that a very restricted form (width five) can accept all languages contained in NC 1 . A branching program is a...
Cite
Text
Bshouty et al. "On Learning Width Two Branching Programs (Extended Abstract)." Annual Conference on Computational Learning Theory, 1996. doi:10.1145/238061.238102Markdown
[Bshouty et al. "On Learning Width Two Branching Programs (Extended Abstract)." Annual Conference on Computational Learning Theory, 1996.](https://mlanthology.org/colt/1996/bshouty1996colt-learning/) doi:10.1145/238061.238102BibTeX
@inproceedings{bshouty1996colt-learning,
title = {{On Learning Width Two Branching Programs (Extended Abstract)}},
author = {Bshouty, Nader H. and Tamon, Christino and Wilson, David K.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1996},
pages = {224-227},
doi = {10.1145/238061.238102},
url = {https://mlanthology.org/colt/1996/bshouty1996colt-learning/}
}