ECCC-Report TR21-054https://eccc.weizmann.ac.il/report/2021/054Comments and Revisions published for TR21-054en-usWed, 14 Apr 2021 22:29:12 +0300
Paper TR21-054
| Encodings and the Tree Evaluation Problem |
Ian Mertz,
James Cook
https://eccc.weizmann.ac.il/report/2021/054We 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.Wed, 14 Apr 2021 22:29:12 +0300https://eccc.weizmann.ac.il/report/2021/054