Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-119 | 15th July 2026 20:19

On the CGGRT Criterion for Detecting Bipartite Perfect Matchings in NC

RSS-Feed




TR26-119
Authors: Swastik Kopparty, Shubhangi Saraf
Publication: 15th July 2026 20:20
Downloads: 83
Keywords: 


Abstract:

The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how to detect as well as find perfect matchings in bipartite graphs in NC. In this note we present an arguably simpler-to-state variation of the NC detection criterion of [CGGRT26], with improved parameters.



ISSN 1433-8092 | Imprint