Bipartite Matching Is in NC

Disclaimer from the Author: If you remember nothing else from this site, remember this: quantum computers are not magic bullets that solve all hard problems instantly via massive parallelism.

Quick side note: Please check out Zvi Mowshowitz's comprehensive guide on reforming K-12 education!

$\rightarrow$ ~~Never trust a T-Rex~~ (My thoughts on the White House executive order regarding Quantum Computing).

🏔️ A Positive Update from the Mountains

I am currently in a fantastic mood, spending time at a lovely science camp with my children in the highlands near Big Bear Lake, California. Because of this, I felt like sharing some optimistic news.

Last week, a group of researchers—Chatterjee, Ghosh, Gurjar, Raj, and Thierauf—uploaded a significant paper to the Electronic Colloquium on Computational Complexity. Their work claims to prove that the Bipartite Matching problem belongs to the complexity class NC.

If this proof holds up, it settles a fundamental question in the realms of derandomization and parallel algorithms that has remained unanswered since the 1980s.

🧩 Understanding Bipartite Matching

In a Bipartite Matching scenario, you are presented with:

A set of $n$ men.
A set of $n$ women.
A list of compatible pairings (who is willing to date whom).

The Goal: Determine if every person can be paired with a willing partner, and if so, produce that specific pairing.

Complexity Evolution

The progression of how we solve this problem is quite fascinating:

Approach	Complexity	Note
Brute Force	$O(n!)$	Completely impractical for large $n$ .
Standard Alg.	$\text{poly}(n)$	Taught in intro courses; efficient for sequential processing.
Randomized NC	$\text{poly}(\log n)$	Requires random bits; succeeds with high probability.
Deterministic NC	$\text{poly}(\log n)$	The new claim: fast, parallel, and certain.

Note: The "bipartite" version assumes heterosexual pairings. If the group includes LGBT individuals, it becomes a general graph matching problem. While still solvable in polynomial time, the algorithm (discovered by Edmonds in the 60s) is significantly more complex.

⚡ The Path to NC

The core question was whether we could move beyond standard polynomial time to achieve polylogarithmic time—specifically $\text{poly}(\log n)$ —assuming we have a polynomial number of parallel processors.

In the 80s, researchers like Karp, Upfal, and Wigderson—as well as Mulmuley and the Vazirani brothers (including my former advisor, Umesh)—proved that the answer was "yes," provided the processors had access to random bits and only needed to be correct most of the time.

The recent breakthrough involves derandomizing the Mulmuley-Vazirani-Vazirani approach, proving that both the decision and the construction of the matching can be done in deterministic polylogarithmic time.

Actually read the paper (if I run out of other things to do).

(Special thanks to Gil Kalai for helping me correct an earlier draft of this post.)

🗳️ Political Note: NYC Primary Elections

Today is the primary election in New York City. Many of my most brilliant colleagues in the fields of AI safety and governance are rallying behind Alex Bores for Congress. Some even view him as a critical figure for the future of humanity.

Why Bores?

AI Regulation: He has been a prominent advocate for regulating AI.
Opposition: His stance is so strong that Marc Andreessen’s "Leading the Future" PAC (which opposes AI regulation) has spent millions to stop him.
General Politics: He is a sane, conventional Democrat—more moderate on Israel than his typical base.

If you reside in New York's 12th Congressional District (central Manhattan) and care about the trajectory of AI safety, I encourage you to consider voting for Bores.

💬 Community Discussion

Nabam: I might finally understand this. You argue for AI regulation despite your views on human irrelevance and your critiques of Anthropic or the Pope. The idea of "automating mathematics" isn't provably impossible; it's just unfalsifiable. It's like the 70s promise of the "paperless office" or the promise of an afterlife. We should remember what it means to be human, regardless of what is written in a papal encyclical.

Hamish Peter Todd: Excitedly: Yes! An algorithms-focused post!

Dan: As a voter in NY-12, it's wild to feel like my vote actually matters on a federal level. It's a tough choice because I actually like both leading candidates.

Posted: Monday, June 22nd, 2026 | Category: Announcements, Complexity