3 ms·

> There's Levin's complete one way function [1; Section 4.3]. I think the article also mentions this: > But his construction was “very artificial,” said Eric

> There's Levin's complete one way function [1; Section 4.3]. I think the article also mentions this: > But his construction was “very artificial,” said Eric Allender, a computer scientist at Rutgers University. It is “not something anybody would have studied for any reason other than to get a result like that.” But as a layman to cryptography I don't get what is the significant difference between this finding and Levin's. Is there anyone who can explain this to someone with an undergraduate level of mathematical backgrounds?

samrift 5y ago
> But as a layman to cryptography I don't get what is the significant difference between this finding and Levin's. Is there anyone who can explain this to someone with an undergraduate level of mathematical backgrounds? Here's a massive simplification. Let's say you tell me "Here's a conjecture: since multiplying 2x3 is hard, multiplying any combination of two numbers from 1-5 is hard. I can't prove that it is hard, but if all of them are hard, then my cryptography works!" Levin's complete function approach : "Here's a function that's at least as hard as any given combination of two numbers: (1x2) + (1x2) + (1x3) + (1x4) + (1x5) + (2x3) + (2x4)... [and so on]. If that turns out to be easy, than your conjecture is wrong!" The article states that there is a novel and surprising connection: "Proving the difficulty of multiplying any random combination of numbers under 5 is equivalent to solving this seemingly unrelated (and as yet unsolved) problem in geometry." The two approaches are pretty different and have very different ramifications. While in a lot of cases, the approach of "here's an equivalent problem" doesn't actually help, in some cases it turns out that the equivalent problem is easier to solve. Or that the connection between the two opens up completely new approaches to solutions - or even applications of the math involved. Sometimes just the proof itself causes new connections! Often it takes considerable time before the impacts show themselves.
gnull 5y ago
> I think the article also mentions this My bad, I didn't read the article carefully enough. > I don't get what is the significant difference between this finding and Levin's. I think it's generally very important to find connections between distant and seemingly unrelated fields. And it's even better to express two seemingly separate fields in the same terms. Because then there's a lot of potential to cross apply the techniques which were developed in those fields. You can see the linked result not only as a formal construction of a problem with certain properties, but also as a link between two distant fields and as one of the many steps needed to maybe one day show that those fields are the same thing. One of my theoretician friends likes to say that solutions in mathematics are valuable because of the "moral" they have, i.e. the possibilities and lessons they demonstrate, not because they formally satisfy some conditions. Think of Physics, Chemistry and Biology. Centuries ago they were completely separate fields. A growing plant and a lightning bolt were completely different concepts which seemed to be operated by their own distinct laws and have nothing to do with each other. But as the Science progressed, people learned about the elemental particles and could see now that lightning bolt and a plant are not separate concepts, but only manifestations of the same laws and processes on lower levels. Now Physics, Chemistry and Biology are not completely distinct domains (Richard Feynman would argue that the latter two are sub-fields of Physics) and techniques and findings from one can be sometimes converted to the others.

samrift 5y ago

> But as a layman to cryptography I don't get what is the significant difference between this finding and Levin's. Is there anyone who can explain this to someone with an undergraduate level of mathematical backgrounds? Here's a massive simplification. Let's say you tell me "Here's a conjecture: since multiplying 2x3 is hard, multiplying any combination of two numbers from 1-5 is hard. I can't prove that it is hard, but if all of them are hard, then my cryptography works!" Levin's complete function approach : "Here's a function that's at least as hard as any given combination of two numbers: (1x2) + (1x2) + (1x3) + (1x4) + (1x5) + (2x3) + (2x4)... [and so on]. If that turns out to be easy, than your conjecture is wrong!" The article states that there is a novel and surprising connection: "Proving the difficulty of multiplying any random combination of numbers under 5 is equivalent to solving this seemingly unrelated (and as yet unsolved) problem in geometry." The two approaches are pretty different and have very different ramifications. While in a lot of cases, the approach of "here's an equivalent problem" doesn't actually help, in some cases it turns out that the equivalent problem is easier to solve. Or that the connection between the two opens up completely new approaches to solutions - or even applications of the math involved. Sometimes just the proof itself causes new connections! Often it takes considerable time before the impacts show themselves.

gnull 5y ago

> I think the article also mentions this My bad, I didn't read the article carefully enough. > I don't get what is the significant difference between this finding and Levin's. I think it's generally very important to find connections between distant and seemingly unrelated fields. And it's even better to express two seemingly separate fields in the same terms. Because then there's a lot of potential to cross apply the techniques which were developed in those fields. You can see the linked result not only as a formal construction of a problem with certain properties, but also as a link between two distant fields and as one of the many steps needed to maybe one day show that those fields are the same thing. One of my theoretician friends likes to say that solutions in mathematics are valuable because of the "moral" they have, i.e. the possibilities and lessons they demonstrate, not because they formally satisfy some conditions. Think of Physics, Chemistry and Biology. Centuries ago they were completely separate fields. A growing plant and a lightning bolt were completely different concepts which seemed to be operated by their own distinct laws and have nothing to do with each other. But as the Science progressed, people learned about the elemental particles and could see now that lightning bolt and a plant are not separate concepts, but only manifestations of the same laws and processes on lower levels. Now Physics, Chemistry and Biology are not completely distinct domains (Richard Feynman would argue that the latter two are sub-fields of Physics) and techniques and findings from one can be sometimes converted to the others.