Computing with a full memory: catalytic space

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10286833" target="_blank" >RIV/00216208:11320/14:10286833 - isvavai.cz</a>

Výsledek na webu

<a href="http://iuuk.mff.cuni.cz/~koucky/prof.html" target="_blank" >http://iuuk.mff.cuni.cz/~koucky/prof.html</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Computing with a full memory: catalytic space

Popis výsledku v původním jazyce

We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state when the computation is finished. We show that the extra space can be used in a nontrivial way, to compute uniform $TC^1$-circuits with just a logarithmic amount of clean space. The extra space thus works analogously to a catalyst in a chemical reaction. $TC^1$-circuits can compute for example the determinant of a matrix, which is not known to be computable in logspace. In order to obtain our results we study an algebraic model of computation, avariant of straight-line programs. We employ register machines with input registers $x_1, ..., x_n$ and work registers $r_1, ..., r_m$. The instructions available are of the form $r_i := r_i + u * v$, with $u, v$ registers (distinct from

Název v anglickém jazyce

Computing with a full memory: catalytic space

Popis výsledku anglicky

We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state when the computation is finished. We show that the extra space can be used in a nontrivial way, to compute uniform $TC^1$-circuits with just a logarithmic amount of clean space. The extra space thus works analogously to a catalyst in a chemical reaction. $TC^1$-circuits can compute for example the determinant of a matrix, which is not known to be computable in logspace. In order to obtain our results we study an algebraic model of computation, avariant of straight-line programs. We employ register machines with input registers $x_1, ..., x_n$ and work registers $r_1, ..., r_m$. The instructions available are of the form $r_i := r_i + u * v$, with $u, v$ registers (distinct from

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

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

Proceedings of the 46th Annual ACM Symposium on Theory of Computing

ISBN

978-1-4503-2710-7

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

857-866

Název nakladatele

The Association for Computing Machinery (ACM)

Místo vydání

New York, NY, USA

Místo konání akce

New York, NY, USA

Datum konání akce

31. 5. 2014

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

WRD - Celosvětová akce

Kód UT WoS článku

—