Pebbling, entropy and branching program size lower bounds

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced in [4]. Proving an exponential lower bound for the size of the non-deterministic thrifty branching programs would separate NL from P under the thrifty hypothesis. In this context, we consider a restriction of non-deterministic thrifty branching programs called bitwise-independence. We show that any bitwise-independent non-deterministic thrifty branching program solving BT2(h, k) must have at least 12 kh/2 states. Prior to this work, lower bounds were known for general branching programs only for fixed heights h = 2, 3, 4 [4]. Our lower bounds are also tight (up to a factor of k), since the known[4] non-deterministic thrifty branching programs for this problem of size O(kh/2+1) are bitwise-independent. We prove our results by associating a fractional 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[6] originally in the context of proving lower bounds for read-once branching programs. We also show that the previous lower bounds known[4] for deterministic branching programs for 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 Tree Evaluation Problem when the instances are restricted to have the same group operation in all internal nodes.