Catalytic Computing and Register Programs Beyond Log-Depth

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10515148" target="_blank" >RIV/00216208:11320/25:10515148 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.MFCS.2025.6" target="_blank" >https://doi.org/10.4230/LIPIcs.MFCS.2025.6</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.MFCS.2025.6" target="_blank" >10.4230/LIPIcs.MFCS.2025.6</a>

Result language

angličtina

Original language name

Catalytic Computing and Register Programs Beyond Log-Depth

Original language description

In a seminal work, Buhrman et al. (STOC 2014) defined the class CSPACE(s, c) of problems solvable in space s with an additional catalytic tape of size c, which is a tape whose initial content must be restored at the end of the computation. They showed that uniform TC&lt;sup&gt;1&lt;/sup&gt; circuits are computable in catalytic logspace, i.e., CL = CSPACE(O(log n), 2&lt;sup&gt;O&lt;/sup&gt;(log n&lt;sup&gt;)&lt;/sup&gt;), thus giving strong evidence that catalytic space gives L strict additional power. Their study focuses on an arithmetic model called register programs, which has been a focal point in development since then. Understanding CL remains a major open problem, as TC&lt;sup&gt;1&lt;/sup&gt; remains the most powerful containment to date. In this work, we study the power of catalytic space and register programs to compute circuits of larger depth. Using register programs, we show that for every ϵ &gt; 0, SAC&lt;sup&gt;2&lt;/sup&gt; ⊆ CSPACE (O (log2n/ log log n), 2&lt;sup&gt;O&lt;/sup&gt;&lt;sup&gt;(log1+ϵ n)&lt;/sup&gt;). On the other hand, we know that SAC&lt;sup&gt;2&lt;/sup&gt; ⊆ TC&lt;sup&gt;2&lt;/sup&gt; ⊆ CSPACE (O (log&lt;sup&gt;2&lt;/sup&gt; n), 2&lt;sup&gt;O(log n)&lt;/sup&gt;). Our result thus shows an O(log log n) factor improvement on the free space needed to compute SAC&lt;sup&gt;2&lt;/sup&gt;, at the expense of a nearly-polynomial-sized catalytic tape. We also exhibit non-trivial register programs for matrix powering, which is a further step towards showing NC&lt;sup&gt;2&lt;/sup&gt; ⊆ CL.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA24-10306S" target="_blank" >GA24-10306S: New challenges in streaming, online, and combinatorial algorithms</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-388-1

ISSN

1868-8969

e-ISSN

1868-8969

Number of pages

18

Pages from-to

1-18

Publisher name

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Place of publication

Wadern

Event location

Varšava

Event date

Aug 25, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—