We revisit the problem of counting paths in width-2 planar branching programs. We show that this is hard for Boolean NC1 under ACC0 [5] reductions, completing a proof strategy outlined in [3]. On the other hand, for several restricted instances of width-2 planar branching programs, we show that the counting problem is TC0-complete. We also show that non-planar width-2 programs can be planarized in AC0[2]. Using the equivalence of planar width-2 programs with the reduced-form representation of positive rationals, we show that the evaluation problem for this representation in the Stern-Brocot tree is also NC1 hard. In contrast, the evaluation problem in the continued fraction representation is in TC0. |
| Cite as: Mahajan, M., Saurabh, N. and Sreenivasaiah, K. (2012). Counting paths in planar width 2 branching programs. In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 59-68 |
 (from crpit.com)
(local if available)
|