{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidxz6azslev7vpsfcr2aelpgfeh6qywf4ur6jkrhgkgqq75q27l2e",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mobnipxqdkt2"
  },
  "path": "/report/2026/100",
  "publishedAt": "2026-06-14T15:43:01.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "We show that the bipartite matching problem is in NC. We extend the result to weighted bipartite matching and the computation of the noncommutative rank of a symbolic matrix. In particular, this implies that the decision version of linear matroid intersection is in NC as well. The techniques are based on the polynomial method, inspired from a construction of subspace design by Guruswami and Kopparty (Combinatorica 2016).",
  "title": "TR26-100 |  Bipartite Matching is in NC | \n\n\tRohit Gurjar, \n\n\tRoshan  Raj, \n\n\tThomas Thierauf, \n\n\tAbhranil Chatterjee, \n\n\tSumanta Ghosh"
}