Abstract

Pebbling, Entropy, and Branching Program Size Lower Bounds BALAGOPAL KOMARATH and JAYALAL SARMA, Indian Institute of Technology Madras, Chennai, India 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 k h/2 states. Prior to this work, lower bounds were known for nondeterministic thrifty branching programs 2 only for fixed heights h = 2, 3, 4 [Cook et al. 2012]. We prove our results by associating a fractional