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

Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

quantamagazine.org

Post reply on HN
Print view View original

41–50 of 107 posts

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#41

Post by rickmode »

TheRealPomax wrote: post #35

When of course, in reality rather than clickbaity titles, they only wrote up the final, concise proof using two pages _after_ thinking about, and working on, the problem for seven years, building on decades of specific research combined with seven years of learning new mathematics (new to Huang, not necessarily new to the world) that might offer ways into cracking this problem.

"Simple != easy." --Rich Hickey

The closest I get in my career is striving for the simplest approach to building something in software, which is not all the easy path. The easy path always leads to complexity -- just look at any enterprise software project that's more than a year to two old.

I find the process of striving for simplicity gratifying and reading this article about similar -- but much longer process -- put a smile on my face.

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#42

Post by lostlogin »

uniqueid wrote: post #37
angry_octet wrote: post #31

Earlier quoted context omitted.

I agree, it's extremely distasteful. I feel the author has cut their teeth writing clickbait headlines to make information extraction harder, the way a supermarket puts the milk at the far corner of the store. I want a link/cite to the original paper in the first para.

It reminds me of that interview a few years back 'Ms Bacall, what was it like working with a screen legend like Nicole Kidman?'

For those like me who didn’t get the reference:

http://news.bbc.co.uk/2/hi/entertainment/3640454.stm

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#43

Post by LolWolf »

swagonomixxx wrote: post #30
LolWolf wrote: post #26

The sensitivity conjecture is actually pretty simple to understand, intuitively. (Its reduction to applications, and its proof, of course, are both a little bit more of the "magical" parts so-to-speak.) The 'canonical' way of thinking about it is in terms of the hypercube graph , which is defined in the following way: - The dimension-0 hypercube graph is... just a single vertex. . - The dimension-1 hypercube graph is…

I like graph theory a lot (even though my prof in uni was horrible at teaching it). One thing I like about it is at least we can easily visualize most graphs, as opposed to say, n-dimensional spaces from real analysis. I also like that coloring vertices is a thing, and that so many problems can be represented by graphs and we can apply so many graph algorithms on top of those graph representations. One thing that alw…

> One thing that always makes me laugh though is the terminology in math. Things like "hypercube" just get a chuckle out of me.

Oh just wait until you get to physics ! :)

> I didn't know what the sensitivity conjecture is but your explanation using coloring a graph is very straightforward.

Kidding aside, thank you!

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#44

Post by dstick »

TheRealPomax wrote: post #35

When of course, in reality rather than clickbaity titles, they only wrote up the final, concise proof using two pages _after_ thinking about, and working on, the problem for seven years, building on decades of specific research combined with seven years of learning new mathematics (new to Huang, not necessarily new to the world) that might offer ways into cracking this problem.

In that line of thinking’s defense: do you marvel at the wonders of science and human achievement every time you switch on a lightbulb?

The hardest thing in the world is to explain something in a simple way. With two pages - I say: Bravo!

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#45

Post by Scene_Cast2 »

The concept of sensitivity is actually not too far from the questions asked in ML. "The minimum number of bit flips needed to change the answer" -> adversarial attacks, prediction stability, corner case performance. "Which bit flips are needed to change the answer" -> feature importance.

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#46

Post by ahmedalsudani »

TheRealPomax wrote: post #35

When of course, in reality rather than clickbaity titles, they only wrote up the final, concise proof using two pages _after_ thinking about, and working on, the problem for seven years, building on decades of specific research combined with seven years of learning new mathematics (new to Huang, not necessarily new to the world) that might offer ways into cracking this problem.

Nothing clickbaity about the title. It says two pages without describing how much effort went into those two pages.

Two pages does not imply it's easy. It implies it's elegant, which probably requires a fair amount of effort.

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#47

Post by BugsJustFindMe »

alberto_ol wrote: post #32
anchpop wrote: post #23

Earlier quoted context omitted.

Kind of makes this seem funny in retrospect: > Aaronson and O’Donnell both called Huang’s paper the “book” proof of the sensitivity conjecture, referring to Paul Erdős’ notion of a celestial book in which God writes the perfect proof of every theorem. “I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this,” Aaronson wrote.

A few comments below a guy called Don Knuth claims to have shortened the proof to one page https://www.scottaaronson.com/blog/?p=4229#comment-1815290

And it's actually only half a page. The first bit is an acknowledgement, and the second half is notes including another few acknowledgements.

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#48

Post by sdenton4 »

scythmic_waves wrote: post #5

From Scott Aaronson's blog (linked in the article): > Another Update: In the comments section, my former student Shalev Ben-David points out a simplification [1] of Huang’s argument, which no longer uses Cauchy’s interlacing theorem. I thought there was no way this proof could possibly be made any simpler, and I was wrong! [1] https://www.scottaaronson.com/blog/?p=4229#comment-1813084

Nice! And it's a basically a pigeonhole principle argument.

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#50

Post by robotresearcher »

TheRealPomax wrote: post #35

When of course, in reality rather than clickbaity titles, they only wrote up the final, concise proof using two pages _after_ thinking about, and working on, the problem for seven years, building on decades of specific research combined with seven years of learning new mathematics (new to Huang, not necessarily new to the world) that might offer ways into cracking this problem.

I don't see anyone arguing otherwise, nor is the title clickbait. The concision and comprehensibility of the proof is part of what makes it remarkable. Just like the opposite size and complexity of Wiles' 'Last Theorem' proof was part of its story.
Post reply on HN