Open Research Index

On the CGGRT Criterion for Detecting Bipartite Perfect Matchings in NC

Swastik Kopparty, Shubhangi Saraf

arXivarxiv/2607.15554Jul 17, 2026cs.CCscore 0

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.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.15554
curl -X POST /api/v1/records/arxiv/2607.15554/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.15554/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'