Post by James Cook [home]
April 21, 2021
A few days ago, Ian Mertz and I posted a new paper to ECCC: Encodings and the Tree Evaluation Problem. Here's the abstract:
We show that the Tree Evaluation Problem with alphabet size k and height h can be solved by branching programs of size kO(h/logh)+2O(h). This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception.