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 [EMAIL PROTECTED]
