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

Elegant six-page proof reveals the emergence of random structure

quantamagazine.org

Post reply on HN
Print view View original

101–110 of 178 posts

Re: Elegant six-page proof reveals the emergence of random structure

#101

Post by _8j50 »

Ok, please ELI5 this for me, The very statement that anything at all is random is completley absurd to me, especially from an academic context. Are they using a definition of random that is equivalent to "nearly impossible to predict"? , I mean, yes, from the perspective of a limited observer random things can exist, but in an absolute sense, for something to be random then even with the knowledge of all things past that lead up to an event, you would not be able to find the cause of that event because it was truly random.

Do they mean "unpredictable for humans with known means of predicting"?

You might as well use the term "magical" or "miraculous" if you use "random".

Re: Elegant six-page proof reveals the emergence of random structure

#102

Post by rurban »

As I already commented in the first submission of this article:

Now that's something I can really use in one of my current problems. Calculating a minimal perfect hash by creating acyclic random graphs. This conjecture gives now tresholds when to stop trying creating random graphs and start afresh.

This eg is needed for large perfect hashes in gperf or integer sets in compilers, such as eg. for C switch statements with Unicode. switch in C is only efficient for dense tables, but not sparse. sparse tables are linear, but could be constant. A switch in Pascal was constant, but so far GCC and llvm didn't care. gperf neither.

see http://ilan.schnell-web.net/prog/perfect-hash/algo.html and http://programming.sirrida.de/hashing.html#c_case_of_string

Re: Elegant six-page proof reveals the emergence of random structure

#103

Post by d--b »

_8j50 wrote: post #101

Ok, please ELI5 this for me, The very statement that anything at all is random is completley absurd to me, especially from an academic context. Are they using a definition of random that is equivalent to "nearly impossible to predict"? , I mean, yes, from the perspective of a limited observer random things can exist, but in an absolute sense, for something to be random then even with the knowledge of all things past…

This is mathematics, not physics. You can define stuff that don't "really" exist in the world, but that work for the purpose of calculating stuff.

"randomness" has as much right to exist in a mathematical sense as a "point" or a "plane".

Re: Elegant six-page proof reveals the emergence of random structure

#104

Post by _8j50 »

d--b wrote: post #103
_8j50 wrote: post #101

Ok, please ELI5 this for me, The very statement that anything at all is random is completley absurd to me, especially from an academic context. Are they using a definition of random that is equivalent to "nearly impossible to predict"? , I mean, yes, from the perspective of a limited observer random things can exist, but in an absolute sense, for something to be random then even with the knowledge of all things past…

This is mathematics, not physics. You can define stuff that don't "really" exist in the world, but that work for the purpose of calculating stuff. "randomness" has as much right to exist in a mathematical sense as a "point" or a "plane".

How can you prove something that isn't real? How is randomness defined as a concept in mathematics?

Re: Elegant six-page proof reveals the emergence of random structure

#106

Post by DavidSJ »

_8j50 wrote: post #104
d--b wrote: post #103

Earlier quoted context omitted.

This is mathematics, not physics. You can define stuff that don't "really" exist in the world, but that work for the purpose of calculating stuff. "randomness" has as much right to exist in a mathematical sense as a "point" or a "plane".

How can you prove something that isn't real? How is randomness defined as a concept in mathematics?

Randomness is usually defined in terms of a probability distribution, which is just a measure where the total mass assigned to all elements adds up to 1.

Re: Elegant six-page proof reveals the emergence of random structure

#107

Post by majkinetor »

_8j50 wrote: post #104
d--b wrote: post #103

Earlier quoted context omitted.

This is mathematics, not physics. You can define stuff that don't "really" exist in the world, but that work for the purpose of calculating stuff. "randomness" has as much right to exist in a mathematical sense as a "point" or a "plane".

How can you prove something that isn't real? How is randomness defined as a concept in mathematics?

You can actually only prove unreal things because you impose limitations. Real things can not be proven, but only disproved.

Re: Elegant six-page proof reveals the emergence of random structure

#108

Post by thfuran »

d--b wrote: post #103
_8j50 wrote: post #101

Ok, please ELI5 this for me, The very statement that anything at all is random is completley absurd to me, especially from an academic context. Are they using a definition of random that is equivalent to "nearly impossible to predict"? , I mean, yes, from the perspective of a limited observer random things can exist, but in an absolute sense, for something to be random then even with the knowledge of all things past…

This is mathematics, not physics. You can define stuff that don't "really" exist in the world, but that work for the purpose of calculating stuff. "randomness" has as much right to exist in a mathematical sense as a "point" or a "plane".

Randomness exists in physics as well.

Re: Elegant six-page proof reveals the emergence of random structure

#109

Post by d--b »

Can anyone with a solid CS background comment on whether this relates to P!=NP at all?

I mean this deals with Hamiltonian cycles (which is the focus of a well know NP hard problems). It talks about lower boundaries for randomness (which relates to the information stored in the graph). The article talks about gaps which are logarithmic.

I can't quite articulate it, but somehow intuitively, it sounds like it could connect.

Re: Elegant six-page proof reveals the emergence of random structure

#110

Post by d--b »

thfuran wrote: post #108
d--b wrote: post #103

Earlier quoted context omitted.

This is mathematics, not physics. You can define stuff that don't "really" exist in the world, but that work for the purpose of calculating stuff. "randomness" has as much right to exist in a mathematical sense as a "point" or a "plane".

Randomness exists in physics as well.

I am just responding to the comment which assumes that it doesn't.
Post reply on HN