Decades-Old Computer Science Conjecture Solved in Two Pages
quantamagazine.org
quantamagazine.org
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
Another blog post: https://www.scottaaronson.com/blog/?p=4229
An older HN post: https://news.ycombinator.com/item?id=20338281
The article discusses non-fixed equivalents, though, both a contextual variable length and a quantum super position length bit array.
> 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 which is a potential application domain for this research.
With all the leaks lately from inside those places, it would be nice if some basic math results could make it outside.
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.
As far as I know, all cryptographic hash functions are sensitive to single bit-flips by design.
Finding those inputs is essentially impossible, but for a true 'random oracle ' they are likely to exist.
And I thought they had ways to construct hash functions so that all the inputs of the same length have a different output?
That's trivially impossible for fixed-size hashes, by the pigeon hole principle.
The point being, for at least that case you can guarantee a sensitivity of one bit.
The sensitivity of that string is the minimum number of bits that need to be changed in order to change the output?
Not being snarky - just want to see if I understand. The phrase "how many bits you could flip" is ambiguous.
From the article: "If, say, there are seven different lies you could have told that would have each separately flipped the outcome, then for your loan profile, the sensitivity of the Boolean function is seven."
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!
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
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.
This[0] article might help though.
> Huang knew, as did the broader research community, that the sensitivity conjecture could be settled if mathematicians could prove an easily stated conjecture about collections of points on cubes of different dimensions.
> In 1992, Craig Gotsman, now of the New Jersey Institute of Technology, and Nati Linial of Hebrew University figured out that proving the sensitivity conjecture can be reduced to answering a simple question about cubes of different dimensions: If you choose any collection of more than half the corners of a cube and color them red, is there always some red point that is connected to many other red points?
https://arxiv.org/e-print/1907.00847
(rename to 1907.00847.tex and then latexmk -pdf 1907.00847.tex)
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?
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.
Any feedback is much appreciated!
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....
If I interpret this correctly it's a tighter bound than the original conjecture, so it should allow better optimizations.
Apparently, for ISA with a small number of registers, graph-coloring is not as relevant because spillover is more important.
https://lists.llvm.org/pipermail/llvm-dev/2017-December/1199...
Most importantly, though, Huang’s result lays to rest nagging worries about whether sensitivity might be some strange outlier in the world of complexity measures, Servedio said. “I think a lot of people slept easier that night, after hearing about this.”
I'll have to reread the paper a couple more times, but I think Boolean sensitivity could be related to the security one has around any given need. There may be further implications around how to assess one's strategies for meeting needs, as those would be the individual inputs to the Boolean function of "Is the need for _____ security met?" This could help provide a theoretical framework for designing systems oriented around well-being.