Fractional pebbling and thrifty branching programs

DOI10.4230/LIPICS.FSTTCS.2009.2311MaRDI QIDQ2920118zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Pierre McKenzie, Rahul Santhanam, Dustin Wehr, Stephen Cook

Publication date 24 October 2012

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

zbMATH Keywords

tree evaluationspace complexitypebblingbranching programs

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)

Recommendations

• Pebbling, entropy and branching program size lower bounds
• Pebbling, entropy, and branching program size lower bounds
• scientific article; zbMATH DE number 706832
• Half-integrality, LP-branching, and FPT algorithms
• Half-integrality, LP-branching and FPT algorithms
• scientific article; zbMATH DE number 1283999
• scientific article; zbMATH DE number 2102760
• scientific article; zbMATH DE number 2186831
• scientific article; zbMATH DE number 3913677
• Fractional 0-1 programming and submodularity

Cited in

(4)

• Pebbling, entropy and branching program size lower bounds
• Pebbles and branching programs for tree evaluation
• Pebbling, entropy, and branching program size lower bounds
• Branching Programs for Tree Evaluation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2920118)