ON LEARNING WIDTH 2 BRANCHING PROGRAMS

We prove that strict width two branching programs or SW2 (which are wi dth two branching programs with exactly two sinks, as defined by Borod in et al. (1986)) are properly PAC learnable under any distribution. W e also observe that PAC learning monotone width two branching programs (which are width two branching programs with exactly one rejecting si nk) is as hard as learning DNF formulae. This work refines both the po sitive and negative results of the paper by Ergun ct al. (1995) and an swers one of the open questions in that paper. (C) 1998 Published by E lsevier Science B.V.