Random Data Compressed 100:1 (Guffaw)

Michael Motyka mmotyka at lsil.com
Tue Jan 8 13:27:47 PST 2002


georgemw at speakeasy.net wrote :
>
>On 8 Jan 2002, at 9:51, Michael Motyka wrote:
>
>> Eric Cordian <emc at artifact.psychedelic.net> wrote :
>> >Someone else needs to read the comp.compression FAQ.
>> >
>> >http://www.reuters.com/news_article.jhtml?type=technologynews&StoryID=498720
>> >
>> >-----
>> >
>> >NEW YORK (Reuters) - A Florida research start-up working with a team of
>> >renowned mathematicians said on Monday it had achieved a breakthrough that
>> >overcomes the previously known limits of compression used to store and
>> >transmit data.
>> >...
>> >ZeoSync said its scientific team had succeeded on a small scale in
>> >compressing random information sequences in such a way as to allow the
>> >same data to be compressed more than 100 times over -- with no data loss.
>> >That would be at least an order of magnitude beyond current known
>> >algorithms for compacting data.
>> >...
>> >-- 
>> >Eric Michael Cordian 0+
>> >
>> There may be a way to derive & patch together pseudorandom sequence
>> generators, who knows. If there is anything real about this I wonder how
>> long it takes to compress large blocks of arbitrary input data?
>> Geological time scales anyone?
>> 
>> Mike
>> 
>
>A meaningless question.  As Eric correctly points out, true
>random input simply cannot be compressed, it doesn't matter
>how clever you are or how much time and computing power you
>have access to.  Converseley, if you're just intereted in 
>"compressing"  the results of your own pseudo-random number
>generator, it's trivial to do it instantly, just store the seed
>and the desired file size.
>
>George
>
So what is compression/decompression? Isn't it just finding
corresponding sets using defined procedures, one set being "smaller"
than the other? Which types of procedures are allowed and which are not?

What exactly is random data? Does it have to appear to be random? Does
it have to pass some set of statistical tests to be random? If a string
or bits from a radiation source spells "Merry Christmas and a Happy New
Year" in ASCII is it non-random - a message from above? If a string of
bits from a natural source ( decay etc ) matches a string of bits from
some PRNG is it somehow disqualified as truly random data? 

I think the classification random does not rule out the presence of
local patterns however obscure. If a substring of data happens to match
what is generated by some PRNG then that substring can be "compressed"
to {generator, seed, count}. The geological timescale might be involved
in matching generator outputs to input data sections or deriving
generators for subsections of data.

So, bottom line, my point, while not necessarily practical, was entirely
missed by you even as you summarized it :-)

Here we go :

"As Eric correctly points out, true random input simply cannot be
compressed, it doesn't matter how clever you are or how much time and
computing power you have access to."

This is a statement of belief isn't it? Odd.

Mike





More information about the cypherpunks-legacy mailing list