Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TREE EVALUATION PROBLEM:
Reports tagged with tree evaluation problem:
TR20-056 | 17th April 2020
James Cook, Ian Mertz

Catalytic Approaches to the Tree Evaluation Problem

The study of branching programs for the Tree Evaluation Problem, introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in $[k]$ at each leaf of a complete binary tree and an explicit function in $[k]^2 \to ... more >>>




ISSN 1433-8092 | Imprint