[MilesTeg]

I thought of a potential loophole. What about a non-deterministic extractor? Let's say you can make your program smaller by having only a 1% chance of extracting perfectly. Just submit the program (for an expected) 100 times and claim your prize.

[svantana]

Through the magic of information theory, I can tell you that this particular trick will save you log2(100) = 6.6 bits. Probably not enough to make a difference.

[MilesTeg]

I see. You are right.