Compression theory reference?

[Hadmut Danisch]

On Tue, Aug 31, 2004 at 04:56:25PM -0400, John Denker wrote:

>  4) Don't forget the _recursion_ argument.  Take their favorite
> algorithm (call it XX).  If their claims are correct, XX should
> be able to compress _anything_.   That is, the output of XX
> should _always_ be at least one bit shorter than the input.
> Then the compound operation XX(XX(...)) should produce something
> two bits shorter than the original input.  If you start with a
> N-bit message and apply the XX function N-1 times, you should be
> able to compress each and every message down to a single bit.


I have often heard that example and I used it myself several times.  I
do not use it anymore, because it is not that easy. There's a major
flaw in this example, and therefore it is not really a
counterexample. If the faculty found that flaw I'd be in a bad
position.

You could define some reversible bizarre function f that does exactly
that job, i.e. for a given message m you need to apply f again and
again and after some finite number of calculations you'll find that
f(...f(m)...) = x where x = 0 or 1

So this is possible. Since the function is reversible, let's call
the inverse function f', and you'll find 
m = f'( ... f'(x)...)  where x is still 0 or 1

Ooops. What happened? Why does this work? Because the commonly used
counterexample has a flaw. 

The reason is that you can invert f(...f(m)...) only if you count the 
number of times you applied f. You need to know the number of times in 
order to revert = decompress it, because you need to apply f' exactly that
many times. You don't have any other stop condition. Applying f' is not a
proper recursion, it's an iteration.

So your information is actually stored in this number, not in 0 or 1.
The output of the compression function is not 0 or 1, it is that
hidden number telling how often you need to apply f to reach 0 or 1.

So just give it as a contradiction that there can not be such a
function because it could be recursively applied to result in 
a single bit is insufficient, it is not a contradiction. 

You need to consider the recursion depth and the inversion. But then
it get's so complicated that most people don't understand it anymore.
And the argument, that reaching a single bit recursively is a
contradiction, is gone. You need to store a number. So what? Who says
that this number isn't shorter that the plain message? And suddenly
your back deep in theory.


That's why I don't like that example. It's convincing at a first
glance, but I don't believe that it is correct.






>
>  1) Get a few "expert witnesses" to certify that your position is
> certainly not a personal fantasy.  (I assume German jurisprudence
> has something akin to the US notion of expert witnesses, right?)


I did. Unfortunately I didn't find a german one, because
it is very difficult to find a german professor witnessing against
any other. It's a tight community. 

I found some outside Germany. But they didn't give me a paper with 
signature, just e-mails. Will see whether the court will accept that. 

I've sent those e-mails to the dean of the faculty of computer science
to convince him that the faculty is wrong. As a result, he configured
the mail relay of the faculty to drop any e-mail containing my 
last name anywhere in the header. 


It's ridiculous and I would laugh if it wouldn't be exactly the
faculty that's said to be the best german faculty of computer science.  





>  2) Try to get the burden-of-proof reversed. 

Very difficult. I meanwhile became an expert in german examination law
and it usually requires the examinee to proof that the examiners
opinion is wrong. But since I already have proven several times that
the university was lying intentionally to the court, they might take
that into consideration. After all, I have brought this forward, and 
I have done my duty. Now it should be up to the university to
respond. They didn't comment for more than four years now.


> The opposition
> are claiming that known algorithms do the job.  Get them to be
> specific about which algorithms they are referring to.  Then
> file with the court some disks, each containing 1.44 megabytes
> of data.

They say LZW and MTF. I have already given an example for LZW. 
They don't care. I've told them to take any random string taken 
from /dev/random under Linux. They don't care. The german principle is
that a faculty is always right by definition. 



>  3) Diagram the pigeon-hole argument for the judge.  See
> diagrams below.

I'll try that. Thanks.



regards
Hadmut




---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com