Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Keywords |
|---|---|---|
2012 | CATS | proof strategy,planar width,restricted instance,evaluation problem,continued fraction representation,width-2 program,boolean nc1,stern-brocot tree,width-2 planar,positive rational,reduced-form representation |
Field | DocType | Citations |
Discrete mathematics,Rational number,Combinatorics,Counting problem,ACC0,Planar,Equivalence (measure theory),Mathematics,Branching (version control) | Conference | 2 |
PageRank | References | Authors |
0.37 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Meena Mahajan | 1 | 688 | 56.90 |
| Nitin Saurabh | 2 | 5 | 3.81 |
| Karteek Sreenivasaiah | 3 | 13 | 5.30 |