Catalytic Tree Evaluation From Matching Vectors

Alexandra Henzinger, Edward Pyne, Seyoon Ragavan · 2026

Read Catalytic Tree Evaluation From Matching Vectors by Alexandra Henzinger, Edward Pyne, Seyoon Ragavan (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-14320.txt.

Description

Alexandra Henzinger and two co-authors give a 2026 arXiv catalyst method for tree tests. Two prior routes traded space against time: one used super-log space with super-poly time, while a drop to circuit tests used log free space and poly time but poly catalyst space. The paper betters the second route.

The new catalyst method runs in log free space and poly time, with sub-poly catalyst space, 2 to the power log-to-the-epsilon n, for any epsilon above zero. That opens a fresh attack on placing tree tests in logspace. By a drop of Williams, it also at once betters the run of time by catalyst space, a notable complexity-theory payoff.

Catalog record

CREATORAlexandra Henzinger, Edward Pyne, Seyoon Ragavan
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-14320

Browse the full library · About the Tower of Babel