5 ms·
Usually with things like this, the result is already fairly well established, or close enough at least, within the scale any real-world application would requir
by daxfohl 7y ago
Usually with things like this, the result is already fairly well established, or close enough at least, within the scale any real-world application would require.
You can think of it like the four color theorem. A beautiful theoretical result (though a far less beautiful proof), but the only practical significance is now cartographers know they'll never need that extra crayon....
- Ericson2314 7y agoYes famous conjectures usually already have a wealth of "downstream" results predicated on their truth value. But sometimes the proof technique is itself novel and that can carry over to other fields.
- tathougies 7y agoI think the most interesting point of the paper isn't simply the proof the conjecture but also the sqrt(n) bound. I doubt many downstream results were predicated on that particular bound.
- carlmr 7y ago>Huang’s result is even stronger than necessary to prove the sensitivity conjecture, and this power should yield new insights about complexity measures. If I interpret this correctly it's a tighter bound than the original conjecture, so it should allow better optimizations.
- jbb123 7y agoWell graph coloring in a more general sense is used for things like register allocation in compilers. So any proofs or increase in theoretical knowledge in the area could lead to improvements in that area.
- pradn 7y agoI believe graph-coloring is no longer used for state-of-the-art register allocators, such as the one in LLVM. Apparently, for ISA with a small number of registers, graph-coloring is not as relevant because spillover is more important. https://lists.llvm.org/pipermail/llvm-dev/2017-December/119915.html https://lists.llvm.org/pipermail/llvm-dev/2017-December/1199...
- peckerish 7y agoCartographers know they'll never need that extra crayon only when all relevant regions are contiguous.