Read-Once Branching Programs for Tree Evaluation Problems

DOI10.1145/3282433zbMath1495.68090OpenAlexW2903016260MaRDI QIDQ5205806

Atsuki Nagao, Kazuo Iwama

Publication date: 16 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4475/

zbMATH Keywords

lower boundsbranching programsspace complexityread-once branching programstree evaluation problem

Mathematics Subject Classification ID

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

This page was built for publication: Read-Once Branching Programs for Tree Evaluation Problems