Abstract | ||
---|---|---|
We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al. [2012]. Proving a superpolynomial lower bound for the size of nondeterministic thrifty branching programs would be an important step toward separating NL from P using the tree evaluation problem. First, we show that Read-Once Nondeterministic Thrifty BPs are equivalent to whole black-white pebbling algorithms, thus showing a tight lower bound (ignoring polynomial factors) for this model. We then introduce a weaker restriction of nondeterministic thrifty branching programs called Bitwise Independence. The best known [Cook et al. 2012] nondeterministic thrifty branching programs (of size O(kh/2 + 1)) for the tree evaluation problem are Bitwise Independent. As our main result, we show that any Bitwise Independent Nondeterministic Thrifty Branching Program solving BT2(h, k) must have at least (k2)h/2 states. Prior to this work, lower bounds were known for nondeterministic thrifty branching programs only for fixed heights h = 2, 3, 4 [Cook et al. 2012]. We prove our results by associating a fractional black-white pebbling strategy with any bitwise independent nondeterministic thrifty branching program solving the Tree Evaluation Problem. Such a connection was not known previously, even for fixed heights. Our main technique is the entropy method introduced by Jukna and Zák [2001] originally in the context of proving lower bounds for read-once branching programs. We also show that the previous lower bounds known [Cook et al. 2012] for deterministic branching programs for the Tree Evaluation Problem can be obtained using this approach. Using this method, we also show tight lower bounds for any k-way deterministic branching program solving the Tree Evaluation Problem when the instances are restricted to have the same group operation in all internal nodes. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1145/2751320 | ACM Transactions on Computation Theory (TOCT) |
Keywords | DocType | Volume |
models of computation,pebbling games,branching programs,lower bounds,entropy | Conference | 7 |
Issue | ISSN | Citations |
2 | 1942-3454 | 1 |
PageRank | References | Authors |
0.39 | 11 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Balagopal Komarath | 1 | 4 | 3.16 |
Jayalal M. N. Sarma | 2 | 17 | 9.16 |