2013/05/28 by Vanderzwet, Frank
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1305.6376
Fractional pebbling is a generalization of black-white pebbling introduced recently. In this reasearch paper we solve an open problem by proving a tight lower bound on the pebble weight required to fractionally pebble a balanced d-ary tree of height h. This bound has close ties with branching programs and the separation of P from NL.