Bipartite Matching is in Catalytic Logspace

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="https://doi.org/10.1109/FOCS63196.2025.00022" target="_blank" >https://doi.org/10.1109/FOCS63196.2025.00022</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/FOCS63196.2025.00022" target="_blank" >10.1109/FOCS63196.2025.00022</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bipartite Matching is in Catalytic Logspace

Popis výsledku v původním jazyce

Matching is a central problem in theoretical computer science, with a large body of work spanning the last five decades. However, understanding matching in the time-space bounded setting remains a longstanding open question, even in the presence of additional resources such as randomness or non-determinism. In this work we study space-bounded machines with access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Despite this heavy restriction, many recent works have shown the power of catalytic space, its utility in designing classical space-bounded algorithms, and surprising connections between catalytic computation and derandomization. Our main result is that bipartite maximum matching (MATCH) can be computed in catalytic logspace (CL) with a polynomial time bound (CLP). Moreover, we show that MATCH can be reduced to the lossy coding problem for NC circuits (LOSSY[NC]). This has consequences for matching, catalytic space, and derandomization:•Matching: this is the first well studied subclass of P which is known to contain MATCH, as well as the first algorithm simultaneously using sublinear free space and polynomial time with any additional resources. Thus, it gives a potential path to designing stronger space and time-space bounded algorithms.•Catalytic space: this is the first new problem shown to be in CL since the model was defined, and one which is extremely central and well-studied. Furthermore, it implies a strong barrier to showing CL lies anywhere in the NC hierarchy, and suggests to the contrary that CL is even more powerful than previously believed.•Derandomization: we give the first class C beyond Logspace for which we exhibit a natural problem in LOSSY[C] which is not known to be in C, as well as a full derandomization of the isolation lemma in CL in the context of MATCH. This also suggests a possible approach to derandomizing the famed RNC algorithm for MATCH.Our proof combines a number of strengthened ideas from isolation-based algorithms for matching alongside the compress-or-random framework in catalytic computation.

Název v anglickém jazyce

Bipartite Matching is in Catalytic Logspace

Popis výsledku anglicky

Matching is a central problem in theoretical computer science, with a large body of work spanning the last five decades. However, understanding matching in the time-space bounded setting remains a longstanding open question, even in the presence of additional resources such as randomness or non-determinism. In this work we study space-bounded machines with access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Despite this heavy restriction, many recent works have shown the power of catalytic space, its utility in designing classical space-bounded algorithms, and surprising connections between catalytic computation and derandomization. Our main result is that bipartite maximum matching (MATCH) can be computed in catalytic logspace (CL) with a polynomial time bound (CLP). Moreover, we show that MATCH can be reduced to the lossy coding problem for NC circuits (LOSSY[NC]). This has consequences for matching, catalytic space, and derandomization:•Matching: this is the first well studied subclass of P which is known to contain MATCH, as well as the first algorithm simultaneously using sublinear free space and polynomial time with any additional resources. Thus, it gives a potential path to designing stronger space and time-space bounded algorithms.•Catalytic space: this is the first new problem shown to be in CL since the model was defined, and one which is extremely central and well-studied. Furthermore, it implies a strong barrier to showing CL lies anywhere in the NC hierarchy, and suggests to the contrary that CL is even more powerful than previously believed.•Derandomization: we give the first class C beyond Logspace for which we exhibit a natural problem in LOSSY[C] which is not known to be in C, as well as a full derandomization of the isolation lemma in CL in the context of MATCH. This also suggests a possible approach to derandomizing the famed RNC algorithm for MATCH.Our proof combines a number of strengthened ideas from isolation-based algorithms for matching alongside the compress-or-random framework in catalytic computation.

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

Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs

ISBN

979-8-3315-7132-0

ISSN

—

e-ISSN

—

Počet stran výsledku

13

Strana od-do

360-372

Název nakladatele

IEEE

Místo vydání

Neuvedeno

Místo konání akce

Sydney, Australia

Datum konání akce

14. 12. 2025

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

WRD - Celosvětová akce

Kód UT WoS článku

001711633100016