Decades-Old Computer Science Conjecture Solved in Two Pages

#1

Post by parsimo2010 » Fri, Jul 26, 2019, 2:57 AM UTC

Decades-Old Computer Science Conjecture Solved in Two Pages
quantamagazine.org

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

#2

Post by floatingatoll » Fri, Jul 26, 2019, 3:31 AM UTC

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 blog post: https://www.scottaaronson.com/blog/?p=4229

An older HN post: https://news.ycombinator.com/item?id=20338281

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

#3

Post by dang » Fri, Jul 26, 2019, 3:38 AM UTC

Recently discussed at https://news.ycombinator.com/item?id=20338281.

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

#4

Post by [deleted] » Fri, Jul 26, 2019, 3:53 AM UTC

[deleted]

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

#5

Post by kian » Fri, Jul 26, 2019, 3:57 AM UTC

Is this in any way related to the quantum algorithm for searching a space in √n time?

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

#6

Post by smitty1e » Fri, Jul 26, 2019, 4:04 AM UTC

"This sensitivity research is so woke," George Boole did not say.

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

#7

Post by gigatexal » Fri, Jul 26, 2019, 4:06 AM UTC

What a fascinating article and kudos to Huang for solving it. I’m excited to see what benefits this has in the future for computing. Not many articles do I read all the way through (I’ve the attention span of a fly these days) but this one I did.

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

#8

Post by kwaugh » Fri, Jul 26, 2019, 4:26 AM UTC

kian wrote: post #5

Is this in any way related to the quantum algorithm for searching a space in √n time?

No

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

#9

Post by dang » Fri, Jul 26, 2019, 4:53 AM UTC

smitty1e wrote: post #6

"This sensitivity research is so woke," George Boole did not say.

Could you please stop posting unsubstantive comments to Hacker News?

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

#10

Post by Bootwizard » Fri, Jul 26, 2019, 5:10 AM UTC

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