Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-054 | 14th April 2021 22:25

Encodings and the Tree Evaluation Problem

RSS-Feed




TR21-054
Authors: James Cook, Ian Mertz
Publication: 14th April 2021 22:29
Downloads: 627
Keywords: 


Abstract:

We show that the Tree Evaluation Problem with alphabet size $k$ and height $h$ can be solved by branching programs of size $k^{O(h/\log h)} + 2^{O(h)}$. This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception.



ISSN 1433-8092 | Imprint