Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size
Kristoffer Arnsfelt Hansen · 2008
We revisit the computational power of constant width polynomial size planar nondeterministic branching programs. We show that they are capable of computing any function computed by a ${{\bf \Pi}_2 \circ {\rm \bf CC^0} \circ {\rm \bf AC^0}}$ circuit in polynomial size. In the quasipolynomial size setting we obtain a characterization of ${\rm \bf ACC^0}$ by constant width planar nondeterministic branching programs.