Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Decades-Old Computer Science Conjecture Solved in Two Pages

quantamagazine.org

Post reply on HN
Print view View original

31–40 of 74 posts

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#31

Post by peckerish »

daxfohl wrote: post #11
Bootwizard wrote: post #10

Can anyone explain the significance of this finding? Any technologies that can benefit from the application of this?

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....

Cartographers know they'll never need that extra crayon only when all relevant regions are contiguous.

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#32

Post by imglorp »

Tepix wrote: post #27

Good 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)?

Great 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.

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#33

Post by rocqua »

Tepix wrote: post #27

Good 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)?

Sensitivity 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.

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#34

Post by userbinator »

rocqua wrote: post #33
Tepix wrote: post #27

Good 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)?

Sensitivity 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.

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.

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#35

Post by derefr »

userbinator wrote: post #34
rocqua wrote: post #33

Earlier quoted context omitted.

Sensitivity 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.

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.

Yes, but sensitivity is the wrong measure to prove that. It’s the difference between a big-O and small-o complexity.

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#36

Post by lexpar »

rocqua wrote: post #33
Tepix wrote: post #27

Good 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)?

Sensitivity 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.

"Given any input string, the sensitivity of that string is how many bits you could flip that cause the output to flip."

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.

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#37

Post by mkl »

lexpar wrote: post #36
rocqua wrote: post #33

Earlier quoted context omitted.

Sensitivity 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.

"Given any input string, the sensitivity of that string is how many bits you could flip that cause the output to flip." 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.

The number of single-bit flips that would change the output on their own.

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."

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#38

Post by zeckalpha »

vecter wrote: post #24
zeckalpha wrote: post #22

Earlier quoted context omitted.

A 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.

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 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.

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#39

Post by rocqua »

userbinator wrote: post #34
rocqua wrote: post #33

Earlier quoted context omitted.

Sensitivity 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.

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.

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.

Re: Decades-Old Computer Science Conjecture Solved in Two Pages

#40

Post by SilasX »

rocqua wrote: post #39
userbinator wrote: post #34

Earlier quoted context omitted.

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.

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?

Post reply on HN