alt.hn

6/22/2026 at 10:43:48 PM

Bipartite Matching Is in NC

 https://scottaaronson.blog/?p=9851

by amichail

6/26/2026 at 2:47:21 PM

Many years ago, on Boardgamegeek, there was a game trading system called "Math Trades", where participants would list a number of trades they were willing to make, and they ran some complicated calculations to figure out how to let as many as possible trade.

CS professor Chris Okasaki, known for his book on purely functional data structures, also played board games and he came across this phenomenon. He realized that it could be modelled as a bipartite matching problem, and wrote a MUCH faster program to manage math trades.

https://okasaki.blogspot.com/2008/03/what-heck-is-math-trade...

I guess it can be made even faster now in theory.

by vintermann

6/27/2026 at 3:09:21 AM

I don't think this new result is supposed to be a speedup. It might even be slower than the existing method. Rather, it's a way to get rid of the random number generator that the old algorithm relied on, so it's deterministic unlike the old way. I'm not even sure that it's guaranteed to find the answer, as opposed to finding it with high probability.

It's mostly of theoretical interest except for some possible niche applications, I'd say. For a math trade type of problem, you'd just go ahead and use the old algorithm with an RNG.

Another famous result of this type was AKS primality testing. Randomized algorithms like Miller-Rabin were known for a long time, very reliable, and quite simple to implement, but AKS was an important theoretical advance because it didn't use random inputs. I think everyone still uses Miller-Rabin in practice.

by throwaway81523

6/26/2026 at 5:53:00 PM

The kidney exchange problem isn't bipartite matching but a cycle packing problem (or disjoint cycle cover).

by emil-lp

6/26/2026 at 9:36:26 PM

The math trades still happen regularly at cons, e.g. Origins had one just last week.

by mirashii

6/26/2026 at 10:05:21 PM

Chris okasaki! Was into functional data structures in college, great book and great dude

by sigbottle

6/26/2026 at 2:17:39 PM

This is an awesome result.

For those unfamiliar: NC is the class of problems which can be solved in polylogarthmic depth with polynomial number of logic gates. It is unproven if NC != P similar to P != NP.

by amirhirsch

6/26/2026 at 2:22:30 PM

Yes, but logic gates with constant fan-in, crucially, otherwise that's called AC.

by gignico

6/26/2026 at 3:36:31 PM

I never studied these specific classes, but my immediate intuition is that an n-input fan-in AND or OR gate can be reduced to a tree of 2-input gates with depth O(log(n)), which preserves polylog complexity, so surely AC = NC.

Wikipedia agrees :)

If you specify the exponent of the log, you get a different answer.

by amluto

6/26/2026 at 9:18:40 PM

[flagged]

by fleahunter

6/26/2026 at 3:45:50 PM

So is it a class of problems that can be parallelized well?

by osti

6/26/2026 at 4:10:49 PM

no (in both directions). lots of np/exp problems paralize well and you can be in NC and parallelize really inefficiently (e.g. you can get a 10x speedup, but you need 1000000x the hardware). the better framing is that NC is the class of efficient algorithms that can be sped up near arbitrarily by parallelization

by adgjlsfhk1

6/26/2026 at 4:21:15 PM

Hmm your last sentence seems to exactly agree that it's a class of algos that parallelize well? What does sped up arbitrarily mean? It's still polynomial speed up right?

by osti

6/26/2026 at 5:08:00 PM

It's a difference of degree. People expect something that "parallelizes well" to show near 1-to-1 speedup. Double the hardware, double the speed. This is "you can always speed it up, but the hardware requirements can increase at any polynomial rate".

by chowells

6/26/2026 at 5:18:42 PM

Ah got it. Reread previous comment and that makes sense.

by osti

6/26/2026 at 8:01:12 PM

Yeah it's more of "on a hypothetical infinitely parallel computer, you'll get a big speedup'.

Which is still useful if you can prove a problem is in NC. It's just not quite as strong as people make it out to be.

by dragontamer

6/26/2026 at 1:31:08 PM

[dead]

by kevinten10