Bipartite Matching is in Catalytic Logspace

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

Bipartite Matching is in Catalytic Logspace

Original language description

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.

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

Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs

ISBN

979-8-3315-7132-0

ISSN

—

e-ISSN

—

Number of pages

13

Pages from-to

360-372

Publisher name

IEEE

Place of publication

Neuvedeno

Event location

Sydney, Australia

Event date

Dec 14, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001711633100016