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
| CREATOR | Alexandra Henzinger, Edward Pyne, Seyoon Ragavan |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-14320