48 ms·
Decades-Old Computer Science Conjecture Solved in Two Pages
- floatingatoll 7y agoOn boolean sensitivies: https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/07/Boolean_Sensitivity_FINAL560-1068x1720.jpg 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 https://arxiv.org/abs/1907.00847 Another blog post: https://www.scottaaronson.com/blog/?p=4229 https://www.scottaaronson.com/blog/?p=4229 An older HN post: https://news.ycombinator.com/item?id=20338281 https://news.ycombinator.com/item?id=20338281
- ssalka 7y agoThis is pure intuition, but from reading this I get the sense that this conjecture is some generalization of a fixed point theorem?
- vecter 7y agoCan you explain your intuition for how this relates to fixed points?
- zeckalpha 7y agoA Boolean array is isomorphic to a fixed point number. The article discusses non-fixed equivalents, though, both a contextual variable length and a quantum super position length bit array.
- vecter 7y agoI don't understand what you said, but I and (I assume) GP were talking about https://en.wikipedia.org/wiki/Fixed_point_(mathematics) https://en.wikipedia.org/wiki/Fixed_point_(mathematics)
- zeckalpha 7y agoFrom the article: > Other measures involve looking for the simplest way to write the Boolean function as a mathematical expression, or calculating how many answers the banker would have to show a boss to prove they had made the right loan decision. There’s even a quantum physics version of query complexity in which the banker can ask a “superposition” of several questions at the same time. Figuring out how this measure relates to other complexity measures has helped researchers understand the limitations of quantum algorithms. I assumed you were discussing https://en.wikipedia.org/wiki/Fixed-point_arithmetic https://en.wikipedia.org/wiki/Fixed-point_arithmetic which is a potential application domain for this research.
- vecter 7y agoI'm not seeing the connection between this research and fixed-point arithmetic.
- eob123 7y agoI don’t exactly follow the above either, but I believe fixed point is meant in a different sense here, as in a function f(x) such there a point x0 exists where x0=f(x0). https://en.m.wikipedia.org/wiki/Fixed-point_theorem https://en.m.wikipedia.org/wiki/Fixed-point_theorem
- mschoene 7y agoWell - the eigenvalues (of the adjacency matrix), which are used in the proof, correspond to eigenvectors. Which are fixpoints (or at least fixed linear subspaces) of the corresponding linear function. So there is some "lexical" connection. But apart from that I'm not sure that I share your sense that this is "some generalization of a fixed point theorem". Can you give us more insight?
- dang 7y agoRecently discussed at https://news.ycombinator.com/item?id=20338281 https://news.ycombinator.com/item?id=20338281.
- deleted 7y ago[deleted]
- kian 7y agoIs this in any way related to the quantum algorithm for searching a space in √n time?
- kwaugh 7y agoNo
- smitty1e 7y ago"This sensitivity research is so woke," George Boole did not say.
- dang 7y agoCould you please stop posting unsubstantive comments to Hacker News?
- deleted 7y ago[deleted]
- smitty1e 7y agoI realize that this mid-night remark is in arguably poor taste and would delete it if possible.
- dang 7y agoI wouldn't worry about a single comment. It's just that we're trying for a higher signal/noise ratio than is the default on internet forums, so I'd like to persuade you to be more thoughtful when you post. It's in your interest to do so, because preserving signal/noise is the one thing that can keep HN intellectually interesting for everyone in the community. By the way, it isn't that people here (including us!) have no sense of humor, it's that internet humor tends to grow like weeds, and everyone overestimates how funny their jokes are. scott_s expressed this well a long time ago: https://news.ycombinator.com/item?id=7609289 https://news.ycombinator.com/item?id=7609289.
- gigatexal 7y agoWhat 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.
- Bootwizard 7y agoCan anyone explain the significance of this finding? Any technologies that can benefit from the application of this?
- daxfohl 7y agoUsually 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....
- Ericson2314 7y agoYes 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.
- tathougies 7y agoI 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.
- carlmr 7y ago>Huang’s result is even stronger than necessary to prove the sensitivity conjecture, and this power should yield new insights about complexity measures. If I interpret this correctly it's a tighter bound than the original conjecture, so it should allow better optimizations.
- jbb123 7y agoWell graph coloring in a more general sense is used for things like register allocation in compilers. So any proofs or increase in theoretical knowledge in the area could lead to improvements in that area.
- chmaynard 7y agoA fine article. A great science writer like Dr. Erica Kalrreich can make anything interesting, even theoretical CS. Other articles by this author: https://www.quantamagazine.org/authors/erica-klarreich/ https://www.quantamagazine.org/authors/erica-klarreich/
- Simon_says 7y agoSurprisingly good for a Quanta Magazine article.
- HelloNurse 7y agoIt's an important and interesting but unusually simple mathematical topic that can be explained quite well without dumbing it down, leading to a "surprisingly good" article compared to scientific divulgation in general.
- yeukhon 7y agoWhat is the importance of such problem in real life?
- Exuma 7y agoCan someone explain the 'answer' simply? I 70% understand the initial problem... I think
- fastball 7y agohttps://d2r55xnwy6nx47.cloudfront.net/uploads/2019/07/Boolean_Sensitivity_FINAL560-1068x1720.jpg https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/07/Boolea...
- Exuma 7y agoI read that, but I believe that's describing the problem. Anyone care to explain the answer in a similar simple way? Actually one thing weird wiht that explanation is they call sensitive bits the ones that don't change the output? You'd think it would be the red ones
- fastball 7y agoThat is the solution! See? It's so simple it seems like a formulation of the problem itself! The solution is to think of the input ('001') in terms of an n-dimensional cube, where n is the length of the input. So for example, a binary logic with 5 bits ('01010') would require a 5-dimensional cube. From there, you check whether moving from one input ('00001') to an adjacent input ('00011') causes a flip in the output. If it does, you label it as "red", and if it doesn't, you label it as "blue". Then you merely find the vertex with the highest number of opposite colors, and the number of opposite colors is the sensitivity.
- Tepix 7y agoGood read! Does this new proof have an effect on cryptography given that it's often desirable to have highly sensitive cryptographic functions (you flip one bit in the input and get a very different output)?
- imglorp 7y agoGreat question. Then it follows, if yes, that the state cryptographers may even have solved this long ago but can't disclose it. With all the leaks lately from inside those places, it would be nice if some basic math results could make it outside.
- rocqua 7y agoSensitivity here is defined as Take all possible input strings Given any input string, the sensitivity of that string is how many bits you could flip that cause the output to flip. Now take the /maximum/ of all input string sensitivities. For e.g. a hash function, you'd want either a minimum or something like a 1st percentile.
- userbinator 7y agoFor e.g. a hash function, you'd want either a minimum or something like a 1st percentile. As far as I know, all cryptographic hash functions are sensitive to single bit-flips by design.
- derefr 7y agoYes, but sensitivity is the wrong measure to prove that. It’s the difference between a big-O and small-o complexity.
- rocqua 7y agoIt is definitely a design goal, but I would be very surprised if sha2 did not have 2 inputs that only differ by a single bit, and have the same output. Finding those inputs is essentially impossible, but for a true 'random oracle ' they are likely to exist.
- IshKebab 7y agoCan someone explain this in a slightly less dumbed-down way. Having trouble following all the wooly explanations. So far I get that we have a function that maps from a string of bits to a single bit. The sensitivity of each input bit is the likelihood that it affects the output, summed across all possible inputs. What is the conjecture?
- plg 7y agonice use of a single .tex file to produce the full .pdf https://arxiv.org/e-print/1907.00847 https://arxiv.org/e-print/1907.00847 (rename to 1907.00847.tex and then latexmk -pdf 1907.00847.tex)
- PascLeRasc 7y agoIs sensitivity weighted by which stage it is for multi-stage logic chains? I.E. for the example graphic, we could argue that the output of the OR into the AND is an input, or in the bank loan example it might ask "Are you married?" and if you answer yes it asks how much your partner makes, so it's a second-stage input to the final boolean calculation - is that taken into consideration when calculating sensitivity?
- aesthesia 7y agoNo. To compute sensitivity we consider the entire boolean function abstractly, without any reference to a particular implementation. There are other equivalent implementations of the same function with different arrangements (and numbers) of gates, so this wouldn't necessarily make sense to include. There are measures of complexity that do (at least sort of) take into account the way that you implement a function with gates, and they typically look at the circuit with the fewest gates or the shortest paths that computes the function.
- garfieldnate 7y ago>the new proof is so simple that one researcher summed it up in a single tweet. Didn't look that simple to me! Reminds me of Andrew Ng showing his students the simple one liner to solve the cocktail party problem in Octave. There's a lot represented in that one line of code!
- ghostbrainalpha 7y agoPretty good for an "Amateur Mathematician", I can't wait to see what he does once he goes pro.
- nradclif 7y agoHuang is a professional mathematician at Emory.
- iamcreasy 7y agoHere is an excellent ELI5 on reddit: https://www.reddit.com/r/explainlikeimfive/comments/ci0q00/eli5_the_sensitivity_conjecture_has_been_solved/ https://www.reddit.com/r/explainlikeimfive/comments/ci0q00/e...
- ohduran 7y agoThe history of computer science is dauting. Unlike physics, though, it's the history of incremental innovations that culminated in what we have today. Thus, if you go back in time long enough, things eventually are manageable. A good primer on the history of CS is probably Code, The Hidden Language of Computer Hardware and Software, by Charles Pretzold. I've put together some notes on it here: http://alvaroduran.com/code http://alvaroduran.com/code. Any feedback is much appreciated!