Branching Programs for Tree Evaluation

DOI10.1007/978-3-642-03816-7_16MaRDI QIDQ3182923zbMATH OpenOpenAlexFDO

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

Publication date 16 October 2009

Published in Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL https://www.pure.ed.ac.uk/ws/files/17973729/Braverman_Cook_ET_AL_2009_Branching_Programs_for_Tree_Evaluation.pdf

Mathematics Subject Classification ID

Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Read-once branching programs for tree evaluation problems
• Read-Once Branching Programs for Tree Evaluation Problems
• Pebbles and branching programs for tree evaluation
• Fractional pebbling and thrifty branching programs
• Pebbling, entropy, and branching program size lower bounds

Cites work

• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• An observation on time-storage trade off
• Branching Programs and Binary Decision Diagrams
• Computational Complexity
• scientific article; zbMATH DE number 4045650 (Why is no real title available?)
• scientific article; zbMATH DE number 3622921 (Why is no real title available?)
• Incremental branching programs
• On lower bounds for read-\(k\)-times branching programs
• On the Tape Complexity of Deterministic Context-Free Languages
• Storage requirements for deterministic polynomial time recognizable languages
• Super-logarithmic depth lower bounds via the direct sum in communication complexity

Cited in

(6)

• Pebbles and branching programs for tree evaluation
• Read-once branching programs for tree evaluation problems
• scientific article; zbMATH DE number 1881085 (Why is no real title available?)
• Length of polynomials over finite groups
• Read-Once Branching Programs for Tree Evaluation Problems
• Pebbles and branching programs for tree evaluation

This page was built for publication: Branching Programs for Tree Evaluation

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