Shtetl-Optimized " Blog Archive " Bipartite matching is in NC!

Shtetl-Optimized

The Blog of Scott Aaronson

If you take nothing else from this blog: quantum computers won't<br>solve hard problems instantly by just trying all solutions in parallel.<br>Also, please read Zvi Mowshowitz's masterpiece on how to fix K-12 education!-->

" Never trust a T-Rex

Bipartite matching is in NC!

Since I’m a good mood today—at a beautiful science camp with my kids, high in the mountains near Big Bear Lake in California—I thought I’d blog about something positive. Last week, five authors posted a major paper to the Electronic Colloquium on Computational Complexity, which shows (or anyway, credibly claims to show) that the Bipartite Matching problem is in the complexity class NC. Assuming this stands, it resolves a central problem in parallel algorithms and derandomization that’s been open since the 1980s.

In Bipartite Matching, you’re given a list of n men and n women, you’re told who’s willing to date whom, and your goal is to

decide whether it’s possible to pair everyone off with a willing partner, and

if they are, actually pair them off.

One of the great early discoveries of combinatorial algorithms, taught in every introductory algorithms course, is that this problem is solvable in time polynomial in n, even though the naïve, brute-force approach would require examining n! possibilities.

(Note that in the bipartite version, we assume that the men and women are all straight. If the men and women can be LGBT, we get the problem of matching in general graphs, which again turns out to be solvable in polynomial time, but now the algorithm is much more sophisticated, and was a major discovery of Edmonds in the 1960s.)

Anyway, the question is whether we can do even better than polynomial time: in particular, can we solve the problem in logarithmic time, given polynomially many parallel processors?

Back in the 1980s, Ketan Mulmuley, my former PhD adviser Umesh Vazirani, and Umesh’s brother Vijay Vazirani managed to show that the answer is yes, but only if the parallel processors additionally get access to random bits, and only need to succeed with high probability.

The new achievement is to derandomize Mulmuley-Vazirani-Vazirani, and show that problems 1 and 2 above are both solvable in deterministic logarithmic time with parallel processing (in other words, in the complexity class NC).

No, I don’t understand how it works yet. If anyone does, feel free to explain in the comments! Or ask your favorite AI to generate a summary. If I run out of options, at some point I might actually try reading the paper.

One other announcement: Tomorrow is the day of primary elections in NYC! Virtually all of my smartest friends who work on AI governance and safety are extremely excited about the Congressional campaign of Alex Bores—indeed, it would be little exaggeration to say that they consider him the last best hope of humankind. Bores has been a national leader on trying to regulate AI, to the extent that Marc Andreessen’s "Leading the Future" anti-AI-regulation PAC has spent millions of dollars trying to sink his candidacy. Outside of AI, Bores seems like a sane, conventional Democrat, i.e. the kind I like, and much more moderate than his base on Israel (note that his main opponent is also such). Without commenting on Bores’ views on every possible issue, I’ll simply say: if you live in New York’s 12th Congressional District (comprising a huge chunk of central Manhattan), and you care about AI safety, please consider a vote for Bores while there’s still time.

Follow

This entry was posted<br>on Monday, June 22nd, 2026 at 12:27 pm and is filed under Announcements, Complexity.<br>You can follow any responses to this entry through the RSS 2.0 feed.

You can leave a response, or trackback from your own site.

5 Responses to "Bipartite matching is in NC!"

Nabam Says:

Comment #1 June 22nd, 2026 at 2:07 pm

Now I might finally get it.

You really insist that AI must be regulated, despite your polemics

about the pope and Olah and Anthropic, and despite your melancholy

views on human irrelevance.

And that’s a very comforting stance.

Because unfortunately, contrary to (first glance) appearances, the

PR pitch of

"automatization of mathematics" is not provably impossible.

It "only" provably fails to be falsifiable (by some Kolmogoroff

complexity or Chaitin number yoga, I’d say everybody will have

a hard time refuting the idea that whatever AI proves was to

a non-negligible extent hidden

in the inputs and won’t be "renewed" if we "switch off" the human

math researchers. Nor can anybody rule out the contrary).

Fine. So the PR is not science. Surprise!

Rather, it’s on a par with: "technically usable nuclear fusion

is around the corner" or my all-time favorite from the 1970s:

"We’re close to having the paperless office! It will arrive in no time."

Or, if you wish, you could compare it to naive promises of an afterlife.

But there’s...