[HN Gopher] Mathematician Solves Sensitivity Conjecture in Two P...
___________________________________________________________________
Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
Author : kjhughes
Score : 211 points
Date : 2021-02-12 15:45 UTC (7 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| LolWolf wrote:
| 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 two vertices connected by a
| single edge. [?]-[?]
|
| - The dimension-2 hypercube graph is four vertices, connected in
| a square pattern: [?]-[?] | |
| [?]-[?]
|
| - The dimension-3 hypercube graph is the graph representing a
| cube!
|
| - The dimension-4 hypercube graph is the graph which takes a
| cube, makes a copy, and then connects the corresponding vertices.
|
| ...
|
| - The dimension-n hypercube graph is the graph which takes a
| dimension-(n-1) hypercube graph, makes a copy, and connects the
| corresponding vertices.
|
| Ok, so let's play a game (for now, think about the 3-dimensional
| cube graph as a concrete example): if you could color the
| vertices of the cube red or green, what is the largest number of
| red (or green) vertices you can find such that no two of the same
| color are adjacent to each other? Note that the 3D hypercube has
| 23=8 vertices, and, more generally, the nD hypercube has 2n
| vertices, so you have a lot of vertices to color :)
|
| So, it turns out (and I will give it to you as an exercise!) that
| you can color 2n-1 vertices of the cube with two colors without
| any vertices of a single color being adjacent to each other,
| _but_ , if you try changing _the color of any one vertex_ then at
| least one of the colors will have (at least) [?]n neighbors that
| are the same color! (It may be worth reading this once or twice
| :)
|
| This is the sensitivity conjecture! The fact that changing any
| one color would immediately imply that now you have at least [?]n
| neighbors that are all of the same color. (This is a slightly
| funky restatement of it, the usual one is in terms of subgraphs
| or boolean functions, but one is easily mapped to the other.)
|
| It turns out a lot of important problems (in things like voting
| systems, for example) can be reduced to proving this conjecture,
| which gives a rather neat set of results "for free" when proving
| it, and why it's been such an interesting object for the past
| uhh, quite a few years in computer science :)
| LolWolf wrote:
| This is a bit of a random comment @dang, but it's always a bit
| of a shame when a long explanation gets posted and the comment
| that it is responding to dies or is downvoted for some reason
| or another. I've seen this happen a few times and am wondering
| if there is a possible fix?
|
| I guess this is the risk one takes when responding to comments,
| but it feels like there might be a reasonable tradeoff/possible
| solution! :)
| dang wrote:
| Yes, it's a problem. We can do things but unfortunately
| they're all manual for now, so we have to know about it, and
| that's a bottleneck. Thanks for letting us know!
| dang wrote:
| This subthread was originally in reply to
| https://news.ycombinator.com/item?id=26116077 but we detached
| it so that it can float freely to a higher place.
| swagonomixxx wrote:
| 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 always makes me laugh though is the terminology
| in math. Things like "hypercube" just get a chuckle out of me.
|
| I didn't know what the sensitivity conjecture is but your
| explanation using coloring a graph is very straightforward.
| LolWolf wrote:
| > 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!
| Agentlien wrote:
| I remember when this came out. I read the paper out of curiosity
| and was amazed how simple it was to follow, even though I hadn't
| even heard of the sensitivity conjecture before. It's beautiful.
| TheRealPomax wrote:
| 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.
| robotresearcher wrote:
| 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.
| jessriedel wrote:
| I suppose the title could be slightly more accurate by
| replacing "solves" with "proves", but I think it's fine. The
| fact that proof is only 2 pages long is highly notable. This is
| not a case of a headline making a typical event look more
| notable than it is.
| rickmode wrote:
| "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.
| breck wrote:
| The hard part about new simple things is getting people to
| understand the implications. Most people will shrug off
| something new and simple as the same as just another new
| complexity, when the implications are vastly different.
| dstick wrote:
| 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!
| ahmedalsudani wrote:
| 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.
| smnrchrds wrote:
| _In his Lettres Provinciales, the French philosopher and
| mathematician Blaise Pascal famously wrote:
|
| I would have written a shorter letter, but I did not have the
| time._
|
| https://www.npr.org/sections/13.7/2014/02/03/270680304/this-.
| ..
| [deleted]
| bidirectional wrote:
| It's been interesting to watch the rapid degradation of the
| term clickbait, we've quickly gone from the original targets
| of the term ("Local mother discovers one small trick", "He
| did X, you WON'T believe what happened next"), to it now
| being used in probably a third of HN's comment sections to
| describe any title which is even mildly editorialised and not
| a longwinded statement of plain facts.
| totalZero wrote:
| ^^ the No True Clickbait fallacy
|
| Personally I feel that the mathematician should have used
| smaller font. Could have gotten it down to one page.
| ahmedalsudani wrote:
| Same with troll. Anybody you disagree with is a troll
| nowadays.
|
| Thinking about it some more, that also applies to "alt-
| right", "SJW", "Nazi", ...
| xmprt wrote:
| If anything I think the term clickbait is used more
| appropriately now. "Local mother discovers one small trick"
| is terrible clickbait because most people are used to it
| now in the same way a Nigerian prince scam won't work on
| most people.
|
| Clickbait is anything that gets you to click on an article.
| In some cases, it can be good clickbait and an equally good
| article and in other cases it can be bad clickbait where
| the title states facts but the facts are misleading or
| require a specific interpretation or need more context or
| don't accurately describe the essence of the article.
| ErikVandeWater wrote:
| The connotation of clickbait is essential to its
| definition.
| crb002 wrote:
| Is there an OEIS sequence? Seems like something there should be
| nice combinatorial formulas for at the different levels of
| sensitivity.
| dls2016 wrote:
| I never learned Fourier analysis of boolean functions... but this
| result smells like an uncertainty principle.
| rsp1984 wrote:
| Should add (2019) to the title.
| dang wrote:
| It's there now. Thanks!
| Scene_Cast2 wrote:
| 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.
| adamnemecek wrote:
| " I find it hard to imagine that even God knows how to prove the
| Sensitivity Conjecture in any simpler way than this."
|
| Why is there a tendency to invoke God in math?
| ColinWright wrote:
| It's a shortcut, they're not literally invoking "God". It's an
| encoding of:
|
| _We don 't know what the optimum is, but we can imagine the
| complete set of possible things, and from those there will be
| one that's best. So that's the optimum, and we want to refer to
| it. We don't know what it is, but we assume it exists, so let's
| just call it 'God's solution'_
| blt wrote:
| > _we can imagine the complete set of possible things, and
| from those there will be one that 's best._
|
| Not necessarily, unless we make some more assumptions about
| the set of proofs and/or the proof goodness function ;)
| erdevs wrote:
| Mathematics often deal in abstractions, and "God" may be used
| as a linguistic abstraction for ideal or perfect knowledge.
| It's a shorthand in writing casually about the most elegant
| mathematical insights. Its use is also a tradition via Erdos
| with "The Book", which Aaronson and many mathematicians pay
| homage to.
| adamnemecek wrote:
| I understand what it means, but I still don't like it.
| AlanYx wrote:
| If it's any consolation, Erdos himself said in one famous
| lecture that the "God" part is irrelevant: "You don't have
| to believe in God, but you should believe in The Book."
| michannne wrote:
| Right. AFAIK there is no universal Math deity like there is
| Caissa for chess that can serve as a representation of
| "perfect math", God is the next best thing.
| GuB-42 wrote:
| In most religions, God is an omnipotent, omniscient, and
| generally perfect being.
|
| Mathematicians simply borrowed that definition. For example,
| Rubik's cube "God's number" is 20. Because, of course, God, as
| an omniscient, omnipotent perfect being will solve the puzzle
| in the minimum possible amount of moves. And that number is 20
| in the most complex case.
|
| Computer science have a similar, more formal concept with
| oracles. An oracle is a machine that can quickly solve a
| problem. How it does it is not the question, it can be
| supernatural, but we simply assume that such a machine exists
| in order to study some theoretical problems.
| scythmic_waves wrote:
| I think about this sometimes. I think it's related to my
| interest in the philosophy of mathematics. From the SEP article
| [1]:
|
| > Bernays observed that when a mathematician is at work she
| "naively" treats the objects she is dealing with in a
| platonistic way. Every working mathematician, he says, is a
| platonist (Bernays 1935).
|
| I think that's why. There's a tendency to think of mathematical
| objects platonically. And given that it would be very odd if
| platonic, mathematical objects interacted causally with our
| universe, well, it's a short hop, skip, and a jump over to that
| meaning they're things a God made. And here I mean "God" in a
| root-of-all-things sense, not a Judeo-Christian or similar
| sense.
|
| Also, I don't think you deserve the downvotes you're getting.
| There may be a tone of condescension, and there may not be. But
| there's a totally charitable way of interpreting that question
| -- you noting a trend that you perceive -- and that's how I
| took it.
|
| [1] https://plato.stanford.edu/entries/philosophy-mathematics/
| QuesnayJr wrote:
| Because it sounds good rhetorically. It is similar to the
| tendency to declare someone who's really good at X "the god of
| X".
| gchamonlive wrote:
| I think that would be because God is nature (for those who
| believe in God) and math is how humans describe nature. That
| would be the same as saying that nature can't be expressed in
| its own language any simpler than this.
| unixbeard1337 wrote:
| What aspect of nature does the sensitivity conjecture
| describe?
| gchamonlive wrote:
| What do you suppose is the answer to this question, other
| than the Conjecture itself?
|
| I was talking about nature as in "the universe we live in".
| Answering that question is just describing the problem
| itself.
| sethc2 wrote:
| I think it's because God is often seen as the infinite, or
| uncreated, or all that can be known. The something that exists
| apart from any material existence.
|
| Mathematical relationships and patterns have this quality.
|
| Really what I wonder is why can't we all just believe in god
| again?
|
| Even if it was just to recognize the fact that there are things
| that exist in an immaterial way. That there are things that are
| good and true and beautiful whose goodness truth and beauty is
| not quantifiable or reduced to some set of atoms. We might
| disagree on what things are better physical manifestations of
| the immaterial things, but we don't need to disagree on their
| existence.
|
| Though I think it is because so many people have said "god is
| like this" and then posit some religious thing that affirms
| their often heinous actions, that people have chosen to say
| yeah I don't believe in that.
|
| But it seems sad that we can't just talk about god in the sense
| of there are things bigger than ourself, even if we don't know
| them because they are unknowable.
|
| Even if we just acknowledged "God" as the first cause or the
| existence of things not material (like 2+2=4 is true even if
| there was no material thing to represent it), I feel like we
| could go a long way to finding that us humans, usually have
| more in common than we have not in common. That the things that
| divide us are actually smaller than the thing that unites us.
|
| (I don't see why your question was downvoted by the way)
| soledades wrote:
| FWIW, most mathematicians surveyed are "Mathematical
| Platonists," meaning they believe that mathematical objects
| exist in a way outside the human mind/the physical universe.
|
| This mathematical "realm" is a very natural home for the
| variety of God a mathematician is likely to imagine.
|
| Alternatively, if you like, God is one of the most powerful
| metaphors we as humans have.
| great_wubwub wrote:
| FFS take a few seconds and read the article.
|
| "Aaronson and O'Donnell both called Huang's paper the "book"
| proof of the sensitivity conjecture, referring to Paul Erdos'
| notion of a celestial book in which God writes the perfect
| proof of every theorem. "
|
| and read the article that sentence links to.
| the_local_host wrote:
| It's not a terrible question, and even if the reference to
| God is via Erdos, there's still a reference. I think it's
| evident in the sciences as well, e.g. "God does not play dice
| with the universe."
| yesenadam wrote:
| > FFS take a few seconds and read the article.
|
| Please read the HN guidelines.
| https://news.ycombinator.com/newsguidelines.html
| scythmic_waves wrote:
| I think that's just another example of what OP is referring
| to. Erdos, a mathematician, invoked God.
| AnHonestComment wrote:
| I don't get the question.
|
| Are we asking why some people in a largely Christian
| society refer to God as a concept?
|
| That answer seems obvious.
|
| Are we asking why some people playfully refer to quotes
| from famous people when giving praise?
|
| Again, that seems obvious.
|
| What, specifically, is being asked?
|
| OP hasn't shown that mathematicians refer to God any more
| often than society at large.
| diffeomorphism wrote:
| A) There isn't.
|
| B) It is a figure of speech that somewhere there is a book of
| "perfect" proofs/blueprint of the universe. Presumably whatever
| concept you call "God" has access to this, just like "Death"
| has a list of all living things etc..
| [deleted]
| tevlon wrote:
| For the interested. Here is an online lecture from the author of
| the paper: https://www.youtube.com/watch?v=EJoe4qH6kLs
| lukeholder wrote:
| And here is the paper:
| http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pd...
| wenc wrote:
| I remember this article from 2019. I remember the writing style
| struck me then as being a little strange.
|
| My first thought was "who's the mathematician"? But the article
| doesn't actually mention the author's name until a few paragraphs
| down, electing instead to put the spotlight on Scott Aaronson and
| other commentators. I felt then as I do now that it was a little
| lacking in respect.
| JadeNB wrote:
| To be fair, it does link to the paper in literally the first
| words, which is in some sense the most important thing. But
| let's go ahead and record the name here since the article takes
| its time: the solver is Hao Huang.
| [deleted]
| gorkish wrote:
| Yes! How hard is it to have a headline that says "Mathematician
| Hao Huang solves Sensititvity Conjecture"? It's nearly
| impossible to distinguish news stories from the force-fed
| advertorials as it is. Now journalists are electing to imitate
| them?! "Texas Teacher Discovers Mortgage Loophole" indeed....
| kevinskii wrote:
| I read it as more of an attempt to frame Hao Huang's
| accomplishment in a way that a lay audience could better
| appreciate it. I didn't get any sense that it was
| disrespectful.
| angry_octet wrote:
| 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.
| uniqueid wrote:
| It reminds me of that interview a few years back 'Ms Bacall,
| what was it like working with a screen legend like Nicole
| Kidman?'
| lostlogin wrote:
| For those like me who didn't get the reference:
|
| http://news.bbc.co.uk/2/hi/entertainment/3640454.stm
| jstanley wrote:
| > I want a link/cite to the original paper in the first para.
|
| I'm guessing this might have changed since you wrote your
| comment, but the very first sentence does contain a link to
| the paper.
|
| The paper itself is longer than 2 pages (but not by a lot!)
| but the "Proof of the main theorem" section is only 2 pages
| long.
| PartiallyTyped wrote:
| > the way a supermarket puts the milk at the far corner of
| the store
|
| I never noticed, but I can only recall a single instance from
| a set of 10 or so where that isn't the case.
|
| Any links on related content to the topic?
| jldugger wrote:
| There's a econtalk or maybe a planet money that goes into
| detail on this: the cold chain is super important in food
| safety, especially for stuff like milk. You want to be able
| to move from refrigerated milk truck to grocery store food
| fridge rapidly, so you put the milk near the loading dock.
| And of course, you keep the loading dock as far away from
| customers as possible so they're not inconvenienced.
|
| Moving the cold chain closer to checkout involves
| additional expenses, so it works more for higher margin
| products, and ones a bit more forgiving if there's a thaw,
| like Coke, Monster energy drinks, and canned coffee from
| Starbucks.
|
| So the question becomes: would you pay 50 cents more for
| milk from a fridge at checkout, when you can get the same
| thing at the back?
|
| EDIT: it was the host of econtalk, appearing on NPR Planet
| money:https://www.npr.org/2014/08/01/337034378/everyone-
| goes-to-th...
| enjoyyourlife wrote:
| The name of the mathematician is Hao Huang
| xiaodai wrote:
| Huang Hao. Chinese family nameXing first
| pundesigner wrote:
| Had a similar experience with another (also Quanta?) article
| last year about some optical physics breakthrough made at my
| not-very-well-known alma mater, but the article was written as
| if the work was all done at MIT, which one of the collaborators
| was affiliated with. You had to scroll to the second page to
| see the name of the institution that the PI was actually at.
| Kaytaro wrote:
| Ironically your comment is guilty as well.
| johntb86 wrote:
| Perhaps it's just that the article isn't written in inverted
| pyramid style? In non-newspaper writing (e.g. a novella) having
| the main character be introduced in the 8th paragraph wouldn't
| be that odd.
| scythmic_waves wrote:
| 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
| knuthsat wrote:
| Knuth reduced it to half a page in the comments
| scythmic_waves wrote:
| HA! I just remembered that that proof was posted to /r/math a
| while back:
|
| https://www.reddit.com/r/math/comments/cl20l6/knuth_has_writ.
| ..
| anchpop wrote:
| 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 Erdos'
| 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.
| alberto_ol 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
| alasdair_ wrote:
| > a guy called Don Knuth
|
| I found this unreasonably funny, given we're posting on a
| tech-focused forum. It's like posting about "a proof by
| some dude called Albert Einstein" on a physics forum. :)
| BugsJustFindMe wrote:
| And it's actually only half a page. The first bit is an
| acknowledgement, and the second half is notes including
| another few acknowledgements.
| hgoury wrote:
| I really enjoyed Ben-David (and Shalev-Schwartz)'s book
| "Understanding machine learning". It's essentially about theory
| though, not "learn all about machine learning in torchsorflow
| in 10 days".
| jcagalawan wrote:
| Different Ben-David. You're talking about Shalev's dad Shai.
| scythmic_waves wrote:
| > I really enjoyed Ben-David (and Shalev-Schwartz)'s book
| "Understanding machine learning".
|
| Good to hear! I only made it partway through (up through the
| kernel trick I think) but I keep meaning to come back to
| finish it.
|
| > torchsorflow
|
| Lol
| sdenton4 wrote:
| Nice! And it's a basically a pigeonhole principle argument.
| master_yoda_1 wrote:
| Frankly speaking I don't know what the "Sensitivity Conjecture"
| is, and also wondering how many people on HN know about it? Or
| people are upvoting without knowing what it is :) So HN ...
| chmod775 wrote:
| The article explains what it is in simple terms and it isn't
| the first time this article is posted on HN.
| terse_malvolio wrote:
| If only there was a way to know...
___________________________________________________________________
(page generated 2021-02-12 23:00 UTC)