Fractional pebbling and thrifty branching programs

DOI10.4230/LIPICS.FSTTCS.2009.2311zbMath1248.68200OpenAlexW2104757941MaRDI QIDQ2920118

Pierre McKenzie, Rahul Santhanam, Dustin Wehr, Mark Braverman, Stephen A. Cook

Publication date: 24 October 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_59a4.html

zbMATH Keywords

branching programstree evaluationspace complexitypebbling

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

This page was built for publication: Fractional pebbling and thrifty branching programs