10 ms·
Mathematician Solves Sensitivity Conjecture in Two Pages (2019)
- rsp1984 6y agoShould add (2019) to the title.
- dang 6y agoIt's there now. Thanks!
- adamnemecek 6y ago“ 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?
- QuesnayJr 6y agoBecause it sounds good rhetorically. It is similar to the tendency to declare someone who's really good at X "the god of X".
- gchamonlive 6y agoI 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 6y agoWhat aspect of nature does the sensitivity conjecture describe?
- gchamonlive 6y agoWhat 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.
- great_wubwub 6y agoFFS 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 Erdős’ notion of a celestial book in which God writes the perfect proof of every theorem. " and read the article that sentence links to.
- scythmic_waves 6y agoI think that's just another example of what OP is referring to. Erdős, a mathematician, invoked God.
- AnHonestComment 6y agoI 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.
- the_local_host 6y agoIt's not a terrible question, and even if the reference to God is via Erdős, 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 6y ago> FFS take a few seconds and read the article. Please read the HN guidelines. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- diffeomorphism 6y agoA) 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..
- ColinWright 6y agoIt'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 6y ago> 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 ;)
- drdeca 6y agoIndeed, but I expect that that for any theorem, that for some level of proof quality which is attained, that all proofs that are at least that good, all have at most a certain finite length. And, as there are only finitely many proofs of any finite length, then the supremum of proof quality over any proofs of that theorem, is attained. (whether there is usually unique proof which attains it, I don't care to guess.)
- erdevs 6y agoMathematics 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 6y agoI understand what it means, but I still don't like it.
- AlanYx 6y agoIf it's any consolation, Erdős 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 6y agoRight. 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.
- scythmic_waves 6y agoI 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/ https://plato.stanford.edu/entries/philosophy-mathematics/
- soledades 6y agoFWIW, 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.
- sethc2 6y agoI 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)
- GuB-42 6y agoIn 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.
- vlowther 6y agoThe overwhelming majority of religions are not monotheistic and believe no such thing about any given deity. /nitpick
- deleted 6y ago[deleted]
- scythmic_waves 6y agoFrom 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 https://www.scottaaronson.com/blog/?p=4229#comment-1813084
- anchpop 6y agoKind 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.
- alberto_ol 6y agoA 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 https://www.scottaaronson.com/blog/?p=4229#comment-1815290
- BugsJustFindMe 6y agoAnd it's actually only half a page. The first bit is an acknowledgement, and the second half is notes including another few acknowledgements.
- alasdair_ 6y ago> 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. :)
- scythmic_waves 6y ago
- wenc 6y agoI 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.
- deleted 6y ago[deleted]
- angry_octet 6y agoI 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 6y agoIt reminds me of that interview a few years back 'Ms Bacall, what was it like working with a screen legend like Nicole Kidman?'
- lostlogin 6y agoFor those like me who didn’t get the reference: http://news.bbc.co.uk/2/hi/entertainment/3640454.stm http://news.bbc.co.uk/2/hi/entertainment/3640454.stm
- jstanley 6y ago> 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 6y ago
- master_yoda_1 6y agoFrankly 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 6y agoThe article explains what it is in simple terms and it isn't the first time this article is posted on HN.
- terse_malvolio 6y agoIf only there was a way to know...
- Agentlien 6y agoI 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.
- tevlon 6y agoFor the interested. Here is an online lecture from the author of the paper: https://www.youtube.com/watch?v=EJoe4qH6kLs https://www.youtube.com/watch?v=EJoe4qH6kLs
- lukeholder 6y agoAnd here is the paper: http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pd...
- LolWolf 6y agoThe 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 2³=8 vertices, and, more generally, the nD hypercube has 2ⁿ 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 2ⁿ⁻¹ 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 :)
- swagonomixxx 6y agoI 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.
- crb002 6y agoIs there an OEIS sequence? Seems like something there should be nice combinatorial formulas for at the different levels of sensitivity.
- TheRealPomax 6y agoWhen 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.
- jessriedel 6y agoI 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 6y ago"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 6y agoThe 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 6y agoIn 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 6y ago
- Scene_Cast2 6y agoThe 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.
- dls2016 6y agoI never learned Fourier analysis of boolean functions... but this result smells like an uncertainty principle.
- fogof 6y agoJust to emphasize how conceptually easy the proof is when boiled down to its bare essentials, here is the proof in tweet form https://twitter.com/BooleanAnalysis/status/1145837576487612416?s=20 https://twitter.com/BooleanAnalysis/status/11458375764876124...