Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Decades-Old Computer Science Conjecture Solved in Two Pages

quantamagazine.org

Post reply on HN
Print view View original

11–20 of 74 posts

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#11

Post by daxfohl »

Bootwizard wrote: post #10

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

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

#12

Post by ssalka »

floatingatoll wrote: post #2

On boolean sensitivies: https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/07/Boolea... The closing quote: > [Huang] was able to prove that in any collection of more than half the points in an n-dimensional cube, there will be some point that is connected to at least √n of the other points — and the sensitivity conjecture instantly followed from this result The actual paper: https://arxiv.org/abs/1907.00847 Another b…

This is pure intuition, but from reading this I get the sense that this conjecture is some generalization of a fixed point theorem?

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#13

Post by Ericson2314 »

daxfohl wrote: post #11
Bootwizard wrote: post #10

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

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....

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

#16

Post by Double_a_92 »

Bootwizard wrote: post #10

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

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

#17

Post by tathougies »

Bootwizard wrote: post #10

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

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

#18

Post by tathougies »

daxfohl wrote: post #11
Bootwizard wrote: post #10

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

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....

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

#20

Post by vecter »

ssalka wrote: post #12
floatingatoll wrote: post #2

On boolean sensitivies: https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/07/Boolea... The closing quote: > [Huang] was able to prove that in any collection of more than half the points in an n-dimensional cube, there will be some point that is connected to at least √n of the other points — and the sensitivity conjecture instantly followed from this result The actual paper: https://arxiv.org/abs/1907.00847 Another b…

This is pure intuition, but from reading this I get the sense that this conjecture is some generalization of a fixed point theorem?

Can you explain your intuition for how this relates to fixed points?
Post reply on HN