Catalytic Computing and Register Programs Beyond Log-Depth

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Catalytic Computing and Register Programs Beyond Log-Depth

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Catalytic Computing and Register Programs Beyond Log-Depth

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GA24-10306S" target="_blank" >GA24-10306S: Nové výzvy proudových, online a kombinatorických algoritmů</a><br>

Návaznosti

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

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název statě ve sborníku

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-388-1

ISSN

1868-8969

e-ISSN

1868-8969

Počet stran výsledku

18

Strana od-do

1-18

Název nakladatele

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Místo vydání

Wadern

Místo konání akce

Varšava

Datum konání akce

25. 8. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—