News for hackers. Stuff that matters.
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by Bootwizard on Friday July 26, 2019 @01:10AM (#20532506)
Can anyone explain the significance of this finding? Any technologies that can benefit from the application of this?
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by daxfohl on Friday July 26, 2019 @01:32AM (#20532599)
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....

Re:Decades-Old Computer Science Conjecture Solved in Two Pages by Ericson2314 on Friday July 26, 2019 @01:40AM (#20532630)
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.
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by tathougies on Friday July 26, 2019 @02:14AM (#20532764)
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.
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by carlmr on Friday July 26, 2019 @05:11AM (#20533427)
>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.

Re:Decades-Old Computer Science Conjecture Solved in Two Pages by jbb123 on Friday July 26, 2019 @04:43AM (#20533311)
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.
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by pradn on Friday July 26, 2019 @12:30PM (#20536001)
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/1199...

Re:Decades-Old Computer Science Conjecture Solved in Two Pages by peckerish on Friday July 26, 2019 @07:19AM (#20533905)
Cartographers know they'll never need that extra crayon only when all relevant regions are contiguous.
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by tathougies on Friday July 26, 2019 @02:13AM (#20532759)
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
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by Double_a_92 on Friday July 26, 2019 @02:11AM (#20532752)
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.
Re:Decades-Old Computer Science Conjecture Solved in Two Pages by keithnz on Friday July 26, 2019 @03:17AM (#20532969)
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.”

Re:Decades-Old Computer Science Conjecture Solved in Two Pages by crawfordcomeaux on Friday July 26, 2019 @03:57AM (#20533133)
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.