Bipartite Matching is in Catalytic Logspace

Aryan Agarwala, Ian Mertz · 2025

Read Bipartite Matching is in Catalytic Logspace by Aryan Agarwala, Ian Mertz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-09991.txt.

Description

Aryan Agarwala and Ian Mertz prove a 2025 result on matching pairs in a graph with very little free memory. Matching is a core task in computer science, yet its place in tight-space computing stayed open for decades. Catalytic space is extra memory that starts full of data which must be left intact at the end.

The authors show the top bipartite matching task can be done in catalytic log space within a fair time bound. They also link matching to a lossy coding task for set circuits. The result is the first new task placed in this class since it was defined.

Catalog record

CREATORAryan Agarwala, Ian Mertz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-09991

Browse the full library · About the Tower of Babel