June 26, 2026
Match made in math heaven?
Bipartite Matching Is in NC
A decades-old math puzzle may finally be cracked—and the comments are losing it
TLDR: Researchers say they may have solved a famous 1980s-era computer science problem in a faster, more reliable way, which would be a major breakthrough if it holds up. Commenters reacted with a mix of awe, explainer-energy, and nerdy jokes—plus one delightfully random detour into board-game trading lore.
A big new paper dropped, and the brainy internet instantly went into victory-lap mode. The claim? A famous matching problem—basically, finding the best way to pair people or items without chaos—might now be solvable much faster on lots of computers working at once, and crucially, without relying on luck. That open question has been hanging around since the 1980s, so to fans of theoretical computer science, this is less “nice result” and more academic Super Bowl upset.
The comments are where the real flavor kicks in. One reader, amirhirsch, came in with pure hype: “This is an awesome result”, then immediately tried to translate the math-speak for everyone else, explaining that NC is the class of problems that can be solved very quickly if you throw enough parallel hardware at them. In other words: the nerds are excited because this could move a famous problem from “solvable eventually” to “solvable fast in parallel,” which is a huge flex.
Then came the lovable chaos. vintermann swerved from abstract theory into board-game gossip, recalling the old “Math Trades” system on BoardGameGeek, where people listed trades and some behind-the-scenes algorithm tried to maximize happy swaps. It’s the kind of comment-thread move the internet lives for: world-changing math result meets “this reminds me of trading Settlers of Catan.” Even the original post had a wink of self-aware comedy, with the author joking that if all else fails, he might actually have to read the paper. That set the tone perfectly: awe, confusion, and a lot of people grinning while pretending they totally understand what just happened.
Key Points
- •A new five-author paper posted to the Electronic Colloquium on Computational Complexity claims that bipartite matching is in NC.
- •Aaronson says that, if correct, the result resolves a major open problem in parallel algorithms and derandomization dating back to the 1980s.
- •The article explains that bipartite matching is already known to be solvable in polynomial time, while asking whether it can also be solved in deterministic polylogarithmic parallel time.
- •Earlier work by Karp, Upfal, and Wigderson, and separately by Mulmuley, Umesh Vazirani, and Vijay Vazirani, achieved parallel solutions using randomness and high-probability success.
- •Aaronson says the new result derandomizes the Mulmuley-Vazirani-Vazirani approach and separately endorses Alex Bores in the NYC primary due to AI regulation concerns.