Paper 2026/265

Catalytic Tree Evaluation From Matching Vectors

Alexandra Henzinger, Massachusetts Institute of Technology, Stanford University
Edward Pyne, Massachusetts Institute of Technology
Seyoon Ragavan, Massachusetts Institute of Technology
Abstract

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 evaluation (TreeEval) in low space: on the one hand, J. Cook and Mertz (STOC 2024) give an algorithm for TreeEval running in super-logarithmic space $O(\log n\log\log n)$ and super-polynomial time $n^{O(\log\log n)}$. On the other hand, an earlier algorithm of J. Cook and Mertz (STOC 2020), run on a catalytic tape, solves TreeEval in logarithmic $O(\log n)$ free space and polynomial time, but with polynomial $O(\sqrt{n})$ catalytic space. We show that the latter result can be improved. We give a catalytic algorithm for TreeEval with logarithmic $O(\log n)$ free space, polynomial runtime, and subpolynomial $2^{O(\log^\epsilon n)}$ catalytic space (for any $\epsilon > 0$). Our result also implies an improved simulation of time by \textit{catalytic} space, via the reduction of Williams (STOC 2025). Our TreeEval algorithm comes from a framework, inspired by private information retrieval, that generically reduces tree evaluation to two combinatorial objects: matching-vector families and \emph{decoders} (a new object we define that closely resembles decoding polynomials). These ingredients' parameters directly govern an algorithm's resources: the vectors' dimension determines its catalytic space, and the decoder's sparsity determines its free space and runtime. In addition to enabling our new algorithm, this framework explains existing tradeoffs, for example why the Cook–Mertz algorithm needs super-logarithmic space but no catalytic tape. It also lets better matching-vector families or decoders plug in directly to give better algorithms.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
tree evaluationprivate information retrievallocally decodable codes
Contact author(s)
amh @ cs stanford edu
epyne @ mit edu
sragavan @ mit edu
History
2026-11-08: last of 2 revisions
2026-02-15: received
See all versions
Short URL
https://ia.cr/2026/265
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/265,
      author = {Alexandra Henzinger and Edward Pyne and Seyoon Ragavan},
      title = {Catalytic Tree Evaluation From Matching Vectors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/265},
      year = {2026},
      url = {https://eprint.iacr.org/2026/265}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.