Pebbles and Branching Programs for Tree Evaluation

DOI10.1145/2077336.2077337zbMath1322.68059OpenAlexW2134098997MaRDI QIDQ2947557

Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam, Stephen A. Cook

Publication date: 24 September 2015

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

Full work available at URL: https://doi.org/10.1145/2077336.2077337

zbMATH Keywords

lower boundsbranching programslog spaceLogDCFL

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)

Related Items (1)

Unnamed Item

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