Bipartite Matching Is in NC

Comments

Bipartite matching is in NC! Since I'm in 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 (Chatterjee, Ghosh, Gurjar, Raj, and Thierauf) 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 time polynomial in log(n), given polynomially many parallel processors?

Back in the 1980s, first Karp, Upfal, and Wigderson, and then (via a very different method) 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 the Mulmuley-Vazirani-Vazirani algorithm, and show that problems 1 and 2 above are both solvable in deterministic polylogarithmic 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.

(Note: Thanks to Gil Kalai for some corrections to an earlier version of this post.)

One Other Announcement

Today 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.

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 the catch: Not even the popes or the church got away with that, at least not in the beta version. The current pope must have remembered that.

No. The accelerationists are not invincible. And no, mathematics is not about to be automated. Can I prove it? No. Nor can I prove that Musk will not introduce an atmosphere, plate tectonics, a magnetic field and vulcanism on Mars. Or that there is no parallel universe in which I am a fan of Andreessen.

This is a good time for remembering what it means to be human. And that's no less true just because it's also written in the pope's encyclica "Magnifica humanitas".

Comment #2 June 22nd, 2026 at 3:16 pm

Yay, an algorithms post!

Comment #3 June 22nd, 2026 at 3:49 pm

NY-12 voter here – wow, I think this is the first time ever where my vote is actually relevant on the federal stage. This is also one of the truly rare instances where I genuinely like both of the front running candidates, and so the decision has been quite difficult for me.

I was leaning towards Lasher for a while, but I ended up marking Bores on my ballot because of the breathtaking dishonesty of the attack ads that OpenAI/a16z have been bombarding me with. I wouldn't even mind if Lasher won, but I just felt like I couldn't reward Leading The Future's behavior here.

Comment #4 June 22nd, 2026 at 4:39 pm

It's such an exciting result, and I want to comment on two interesting things about it.

This paper is inspired by our recent work "From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids" (STOC2026). Our paper is about subspace design, a central combinatorial object in coding theory. Actually, finding the connection between bipartite matching and our work is a very non-trivial observation, but if one is given that as a hint, I feel like the remaining technical work won't be too hard. It's a similar wisdom like Ryan found breakthrough in tree evaluation leads to time-space simulation.

A small advertisement: If you want to know about this connection and where the ideas come from, I kindly invite you to my talk about this paper at STOC on Thursday. I will try to give a gentle introduction. I will explain how the bipartite matching algorithm works.

Another interesting thing: Before the preprint was posted, I knew this result because authors first announced it at some workshop and I heard about it. Then after I already knew their work is inspired by our work, I can reproduce their first main result. Again I feel like given the existence of the connection the remaining part shouldn't be hard.

Then, I tried to test GPT5.5pro on whether it could reproduce it GIVEN THE CONNECTION TO OUR PAPER. I expected GPT would succeed but it failed! I was surprised but this time I will say it's humanity's success (although maybe just temporary). Huge congrats to the authors!

The prompt I used was suggested by Mehtaab Sawhney in the FirstProof report, so it's not the prompt fault, it's GPT5.5pro's weakness. See the chat history: https://chatgpt.com/c/6a399010-ab24-83e8-8b1b-992391c2c07f (please disregard some summary in Chinese. That's because GPT detected my computer language is Chinese.)

Comment #5 June 22nd, 2026 at 4:44 pm

Oh I should use the sharing link: https://chatgpt.com/share/6a39ac5d-5c84-83e8-87b2-36af77c46b7d

Comment #6 June 22nd, 2026 at 6:00 pm

I think the key bit of the paper is replacing the random weights that Lovasz used with chosen matrices. The nice thing about random weights is that they are random: they don't satisfy any polynomial identities that aren't forced to be true by virtue of being polynomial identities, and so looking at the rank gives the size of the matching. If you can find a deterministic encoding to a ring where this will hold you are done, and the paper finds such an encoding.

Interestingly they don't seem to talk the algebraic geometry language that's pretty clearly at work in some of the stuff.

Comment #7 June 22nd, 2026 at 6:26 pm

I have recently made some nice progress on a different matching problem. One way to describe it: You have a string of open and closing parens like ))((((()()()()(. Each opening paren can be matched with any closing paren to its right in the usual way. Each paren gets a non-negative weight (that is vertices get weights, but edges don't.)

Now my result: you can find a maximum weight matching in O(length of the string) in the comparison model.

Another equivalent formulation: given a sequence of priority queue instructions like insert(X) and delete minimum, we can evaluate in linear time what will be left over in the resulting priority queue at the end in the comparison model. (However figuring out what gets deleted from the queue when is still O(n log n).)

The algorithm I found uses soft heaps in some clever ways to repeatedly shrink the problem by a constant factor. And some matroid dualisation for good measure.

I'm not an academic, so it's taking me a while to write up the paper. (You can contact me at generalbaguette@gmail.com if you are interested. Sorry for the throwaway email address in public.)

Comment #8 June 23rd, 2026 at 12:01 am

The first thing which occurred to me when I saw this result was whether the techniques could generalize to an NC solution to the more general matroid intersection problem. Happily, the authors have already charted much of this territory in the paper, finding that their techniques generalize to linear matroids, which take in the two concrete examples of matroid intersection problems I'm familiar with: bipartite matching itself, and the arborescence problem.

I guess my follow-up question, from the perspective of someone whose matroid theory knowledge is pretty limited, is whether these or other techniques are expected to go further and parallelize the general matroid intersection problem entirely. Are there any special cases of matroid intersection which are known to be P-complete, or otherwise any other known barriers to parallelizing matroid intersection in general?

Comment #9 June 23rd, 2026 at 12:01 am

Is there a nice generalization to polyamory which is still in P?

Comment #10 June 23rd, 2026 at 12:11 am

Patrick #9: The version where you're trying to get everyone into happy sets of three is called 3-Dimensional Matching, and is already NP-complete.

Comment #11 June 23rd, 2026 at 4:41 am

Aren't combinatorics trivially trivial? I thought we already discussed this, unless it has Grothendieck in it I ain't reading! /sarcasm/

Comment #12 June 23rd, 2026 at 5:20 am

@Greg McLellan How do you specify a general, non-realizable, matroid in a short amount of space? The number of matroids on an n element set is something like 2^((2-o(1))^n), so you need exponentially many bits just to write one down.

Comment #13 June 23rd, 2026 at 7:01 am

Are there any problems left for which we have a good (P or NC or whatever notion of goodness you care about) randomized algorithms, but do not yet have a good det algorithm? Polynomial Id testing comes to mind, but I don't know of any other ones.

Comment #14 June 23rd, 2026 at 7:11 am

gasarch #13: Yeah, polynomial identity testing is the big one, but there are many other examples of randomized algorithms that haven't yet been successfully derandomized.

One of my personal favorites is Gurvits's algorithm, for approximating the permanent of a matrix of bounded norm. Actually Jerrum-Sinclair-Vigoda, for approximating the permanent of a nonnegative matrix (and related Markov Chain Monte Carlo algorithms), is another big example.

While this is a slightly different example, Dana mentions getting a deterministic linear-time algorithm for Minimum Spanning Tree (as opposed to n times inverse Ackermann of n) as her own favorite.

Comment #15 June 23rd, 2026 at 8:39 am

David Speyer #12: I'm not sure you need to for the purposes of my inquiry? Matroid oracles of various kinds are commonplace in algorithmic results on the topic, presumably an NC algorithm for matroid intersection could use the same.

But if necessary, I'd expect (encodings of) clocked Turing machines which decide whether an input subset is independent, a basis, a circuit, etc. to suffice. Granted we couldn't reasonably expect general matroid intersection presented in this manner to be P-complete (it appears you would need to go to coNP to verify that a clocked Turing machine decides a system of independent sets), but I did ask whether some special case is known to be P-complete, rather than the general case.

Comment #16 June 23rd, 2026 at 8:52 am

Mulmuley et al. proved that bipartite matching is in the complexity class "randomized NC" or RNC. Is the relationship between RNC and NC the same as the relationship between BPP and P, or is there some subtle distinction between the concepts of "randomized" and "probabilistic"?

Also, I believe that most complexity theorists suspect that P = BPP. Do they also suspect that NC = RNC for similar reasons? Or are logarithmic time and polynomial time different enough animals that the heuristic "randomness doesn't give you a qualitative speedup" doesn't apply in the log-time case? (I realize that this new paper may affect the answer to that question.)

Comment #17 June 23rd, 2026 at 9:40 am

Ted #16: The notation is a weird historic quirk, but "R" means that you can only ever err in one direction, not the other one. So there's also RP for example, which sits between P and BPP (and gets smushed together with them if P=BPP). The MVV algorithm