"This sensitivity research is so woke," George Boole did not say.
Could you please stop posting unsubstantive comments to Hacker News?
[deleted]
Decades-Old Computer Science Conjecture Solved in Two Pages
41–50 of 74 posts
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#42Earlier quoted context omitted.
It 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.
Note: correct me if I’m wrong, but to be relevant to this theorem and definition of sensitivity, the two strings would have to be for the same circuit and therefore be the same length, which is much harder than finding hash collisions in general. And I thought they had ways to construct hash functions so that all the inputs of the same length have a different output?
> 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.
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#43Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#44Can 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?
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#45Good 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)?
Nah. Computing sensitivity has always been easy enough, flip bits and watch output. This is about how to do it in a generalized way that fits in with related work in the field.
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#46Earlier quoted context omitted.
Note: correct me if I’m wrong, but to be relevant to this theorem and definition of sensitivity, the two strings would have to be for the same circuit and therefore be the same length, which is much harder than finding hash collisions in general. And I thought they had ways to construct hash functions so that all the inputs of the same length have a different output?
> 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.
Not if the output is longer than the input, such as for passwords
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#47Earlier quoted context omitted.
> 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.
Not if the output is longer than the input, such as for passwords
I doubt any study of hash functions restricts itself to studying a very tiny subset of all possible (infinite) inputs. The security of hash functions is always studied under the assumption of arbitrary inputs.
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#48Earlier quoted context omitted.
Note: correct me if I’m wrong, but to be relevant to this theorem and definition of sensitivity, the two strings would have to be for the same circuit and therefore be the same length, which is much harder than finding hash collisions in general. And I thought they had ways to construct hash functions so that all the inputs of the same length have a different output?
> 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.
Sorry, I meant all inputs whose length equals the output length.
The point being, for at least that case you can guarantee a sensitivity of one bit.
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#49Earlier quoted context omitted.
Usually 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....
Well 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.
I believe graph-coloring is no longer used for state-of-the-art register allocators, such as the one in LLVM.
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...
Re: Decades-Old Computer Science Conjecture Solved in Two Pages
#50nice use of a single .tex file to produce the full .pdf
https://arxiv.org/e-print/1907.00847
(rename to 1907.00847.tex and then latexmk -pdf 1907.00847.tex)