Bipartite matching is in NC @SimonsInstitute
Bipartite matching is in NC  @SimonsInstitute
Uploaded October 2026 | Updated November 2026, 3 days ago
Roshan Raj (Ohio State University)
https://simons.berkeley.edu/talks/roshan-raj-ohio-state-university-2026-10-28
Derandomization

We show that the bipartite matching problem is in NC. We extend the result to weighted bipartite matching and weighted linear matroid intersection. This in turn helps to show that the search versions of bipartite matching and linear matroid intersection are in NC as well. The techniques are based on a polynomial method, inspired from a construction of subspace design by Guruswami and Kopparty (Combinatorica 2016).
Bipartite matching is in NCDistributional Diffusion ModelsHigh-Dimensional Expansion (HDX) (Part 3)Gap Amplification for Local Hamiltonians with Combinatorial SoundnessLabOS: The AI-XR Co-Scientist That Sees and Works With HumansCoboundary Expansion and Locally Testable Codes (Part 1)Evaluating factuality in long-form generationTalk by Max Hopkins (Institute for Advanced Study)Sampling Sphere Packings with Continuum Glauber DynamicsEntropic independenceAldous-type Spectral Gaps in Unitary GroupsSparse Random Graphs and Random Matrix Statistics (Part 2)
Simons Institute for the Theory of Computing |

Bipartite matching is in NC

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER