Post by James Cook [home]

Encodings and the Tree Evaluation Problem

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 k^O(h/logh)+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.