Read-once branching programs for tree evaluation problems

DOI10.4230/LIPICS.STACS.2014.409MaRDI QIDQ2965502zbMATH OpenOpenAlexFDO

Authors Atsuki Nagao, Kazuo Iwama

Publication date 3 March 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2014.409

zbMATH Keywords

combinatoricslower boundsspace complexityread-once branching programsbranching programs

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Read-Once Branching Programs for Tree Evaluation Problems
• 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

Cited in

(6)

• Branching Programs for Tree Evaluation
• Pebbles and branching programs for tree evaluation
• Pebbling, entropy and branching program size lower bounds
• A unified method for placing problems in polylogarithmic depth
• Read-Once Branching Programs for Tree Evaluation Problems
• Pebbling, entropy, and branching program size lower bounds

This page was built for publication: Read-once branching programs for tree evaluation problems

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