Fractional pebbling and thrifty branching programs

DOI10.4230/LIPICS.FSTTCS.2009.2311zbMATH Open1248.68200OpenAlexW2104757941MaRDI QIDQ2920118FDOQ2920118

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

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

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)

Cited In (4)

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

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)