Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SIZE LOWER BOUNDS:
Reports tagged with Size Lower Bounds:
TR13-006 | 8th January 2013
Balagopal Komarath, Jayalal Sarma

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 by Cook et al.(2011). 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 ... more >>>




ISSN 1433-8092 | Imprint