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.
The kidney exchange problem isn't bipartite matching but a cycle packing problem (or disjoint cycle cover).
amirhirsch 4 hours ago [-]
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.
gignico 4 hours ago [-]
Yes, but logic gates with constant fan-in, crucially, otherwise that's called AC.
amluto 3 hours ago [-]
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.
amirhirsch 3 hours ago [-]
Yes.
There is a beautiful proof of the disjunction between AC0 and NC showing parity cannot be done in AC0 using harmonic analysis of Boolean functions
That paper is in the wiki refs but Hastad’s original is from 1986
osti 3 hours ago [-]
So is it a class of problems that can be parallelized well?
adgjlsfhk1 2 hours ago [-]
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
osti 2 hours ago [-]
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?
chowells 1 hours ago [-]
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".
osti 58 minutes ago [-]
Ah got it. Reread previous comment and that makes sense.
9 minutes ago [-]
kevinten10 5 hours ago [-]
[dead]
Rendered at 18:16:24 GMT+0000 (Coordinated Universal Time) with Vercel.
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.
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.
Wikipedia agrees :)
If you specify the exponent of the log, you get a different answer.
There is a beautiful proof of the disjunction between AC0 and NC showing parity cannot be done in AC0 using harmonic analysis of Boolean functions
That paper is in the wiki refs but Hastad’s original is from 1986