Catalytic Tree Evaluation From Matching Vectors

Alexandra Henzinger, Edward Pyne, Seyoon Ragavan

We give new algorithms for tree evaluation (S. Cook et al. TOCT 2012) in the catalytic-computing model (Buhrman et al. STOC 2014). Two existing approaches aim to solve tree evaluat…