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(k(h/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 (k/2)(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 Zak [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.
