4 ms·

Can anyone explain the significance of this finding? Any technologies that can benefit from the application of this?

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 ago
  Yes 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 ago
  I 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 ago
  Well 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 ago
    I 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 ago
  Cartographers know they'll never need that extra crayon only when all relevant regions are contiguous.
Double_a_92 7y ago
Most of the times the solution of the problem doesn't really matter. The useful bits are the "technologies" that you discovered in order to solve the problem.
tathougies 7y ago
Large boolean decision functions often arise in implementing logical circuits and compilers. I'm not an expert, but I imagine having an upper bound on relations between sensitivity and other metrics may yield insights into optimizations here. Since these problems are often intractable due to NP-completeness, any bounding functions that can offer heuristics can lead to more daring optimizations
keithnz 7y ago
the significant bit is :- Most importantly, though, Huang’s result lays to rest nagging worries about whether sensitivity might be some strange outlier in the world of complexity measures, Servedio said. “I think a lot of people slept easier that night, after hearing about this.”
crawfordcomeaux 7y ago
I'm studying universal needs for life to thrive. My intuition tells me this proof may imply some things about the question "Are all your needs met?" I'll have to reread the paper a couple more times, but I think Boolean sensitivity could be related to the security one has around any given need. There may be further implications around how to assess one's strategies for meeting needs, as those would be the individual inputs to the Boolean function of "Is the need for _____ security met?" This could help provide a theoretical framework for designing systems oriented around well-being.

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 ago
Yes 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 ago
I 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 ago
Well 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 ago
  I 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 ago
Cartographers know they'll never need that extra crayon only when all relevant regions are contiguous.

Double_a_92 7y ago

Most of the times the solution of the problem doesn't really matter. The useful bits are the "technologies" that you discovered in order to solve the problem.

tathougies 7y ago

Large boolean decision functions often arise in implementing logical circuits and compilers. I'm not an expert, but I imagine having an upper bound on relations between sensitivity and other metrics may yield insights into optimizations here. Since these problems are often intractable due to NP-completeness, any bounding functions that can offer heuristics can lead to more daring optimizations

keithnz 7y ago

the significant bit is :- Most importantly, though, Huang’s result lays to rest nagging worries about whether sensitivity might be some strange outlier in the world of complexity measures, Servedio said. “I think a lot of people slept easier that night, after hearing about this.”

crawfordcomeaux 7y ago

I'm studying universal needs for life to thrive. My intuition tells me this proof may imply some things about the question "Are all your needs met?" I'll have to reread the paper a couple more times, but I think Boolean sensitivity could be related to the security one has around any given need. There may be further implications around how to assess one's strategies for meeting needs, as those would be the individual inputs to the Boolean function of "Is the need for _____ security met?" This could help provide a theoretical framework for designing systems oriented around well-being.