Metraipolis › archive › dc_68938fee2195

An Operator Approach to Register Programs for Catalytic Computing — arXiv:2609.18692

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.18692
License (as archived)
CC0-1.0
Archived
2026-10-15T17:11:55.866Z
SHA-256 of the archived text
e0f5ba2f3198718a219588e06ea178db2b90e0a05bdcae326cc943824c7577ea
Stable URL of this page
https://metraipolis.com/documento/dc_68938fee2195

How to cite

An Operator Approach to Register Programs for Catalytic Computing — arXiv:2609.18692 — arXiv (en), https://arxiv.org/abs/2609.18692 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_68938fee2195 (Metraipolis archive dc_68938fee2195, sha256 e0f5ba2f3198718a219588e06ea178db2b90e0a05bdcae326cc943824c7577ea)
BibTeX
@misc{dc68938fee2195,
  title = {An Operator Approach to Register Programs for Catalytic Computing — arXiv:2609.18692},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18692},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_68938fee2195; sha256 e0f5ba2f3198718a219588e06ea178db2b90e0a05bdcae326cc943824c7577ea},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18692. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In a seminal work, Buhrman et al.\ (STOC 2014) introduced catalytic computation and proved that uniform $TC^1$ circuits are computable in catalytic logspace, the class of problems solvable in space $s$ with an additional catalytic tape of size $c$, a tape whose initial content must be restored at the end of the computation. A central ingredient of their proof is the register program model. Namely, they constructed a uniform family of register programs that computes $x^n$ using $n$ registers and four accesses to $x$. Since then, determining the number of registers and input accesses required to compute a polynomial of a given degree has become a central question in the study of catalytic computation. On one hand, we prove that the four-access bound of Buhrman et al.\ is optimal: every passive-output register program computing a polynomial of degree greater than three requires at least four input accesses, independently of the number of registers. On the other hand, we show that their register bound is not optimal. For every $t\geq2$ and every field $K$ of characteristic $0$ or greater than $2t-1$, we construct a register program for $x^{2t-1}$ with four input accesses and $t$ registers. Our proofs rely on derivations and their exponential operators. This approach represents a register program as a series of exponential derivation operators, reducing register restoration to an operator identity. Finally, we use the uniform family of register programs to improve known trade-offs for catalytic streaming algorithms and register programs for matrix powering. The generalization of the lower-bound methods and the construction of the uniform family of register programs were developed with assistance from ChatGPT 5.6.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.18692 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T16:17:44.832Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).