Can someone explain the 'answer' simply? I 70% understand the initial problem... I think
Decades-Old Computer Science Conjecture Solved in Two Pages
51–60 of 74 posts
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#52Is 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?
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#53Earlier quoted context omitted.
Could you please stop posting unsubstantive comments to Hacker News?
I realize that this mid-night remark is in arguably poor taste and would delete it if possible.
I 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.
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#54Is 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?
No. 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.
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#55A 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/
It's interesting to read and extremely accessible to the point that nothing can be learned about the actual problem and its solution.
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#56>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!
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#57Can someone explain the 'answer' simply? I 70% understand the initial problem... I think
https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/07/Boolea...
I 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
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#58Pretty good for an "Amateur Mathematician", I can't wait to see what he does once he goes pro.
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#59Earlier quoted context omitted.
I don't understand what you said, but I and (I assume) GP were talking about https://en.wikipedia.org/wiki/Fixed_point_(mathematics)
From 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 measu…
I'm not seeing the connection between this research and fixed-point arithmetic.
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#60Earlier quoted context omitted.
https://d2r55xnwy6nx47.cloudfront.net/uploads/2019/07/Boolea...
I 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
That 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.