This paper here shows some interesting applications - it is not the first one, but the first non-paywalled one that I found: https://arxiv.org/pdf/cs/0312044.pdf
Cilibrasi's "Statistical Inference through Data Compression" is pretty cool. One nice application was using compression to infer the mutual-information between DNA from different animals, and using that to construct evolutionary trees.
Edit: I see your arxiv link is to the same thing (although I have a hard-copy of the book based on their thesis, so didn't spot it immediately)
There are no useful applications of Kolmogorov complexity, because it's useless (apart from it's though provoking qualities): http://forwardscattering.org/post/7
This problem is solved by choosing a standard language, which requires some way to tell whether one language is "less silly" than another. There's no 'correct' way to judge this, but a reasonable, objective benchmark is how many bits it takes to write a self-interpreter (in a similar spirit to "compiler optimizations should pay for themselves" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.... )
Binary Lambda Calculus is a pretty good for this. I personally prefer Binary Combinatory Logic, but its self-interpreter is a bit longer.
There's probably a way to game this benchmark with a "silly" language, but I imagine anything more complicated than hard-coded literals would end up larger than BLC.
I think there is a mistake in that article: One has to fix a specific language before and then determine the Kolmogorov Complexity of an input - one is not allowed to take a separate Language for each input, unless one also encodes how that Language is calculated from an input, which will take up some space.
This is a bit like saying that SAT is in O(1): One can create a separate program for each instance that answers that instance in constant time.
And the useful applications that I know of (apart from using it as a tool in proving theoretical things) come from replacing the Kolmogorov complexity with a a real compressor that just approximates the Kolmogorov complexity - this produces some empirical results.
> one is not allowed to take a separate Language for each input
They're not defining a different language per input, they're defining a single language, but it's "silly" because it's tailored to favour one specific string. Their point is that we can always construct a universal language which encodes any particular sequence as 1 bit: the language simply checks the first bit of its input, and if it's 0 it returns that sequence; otherwise it ignores that bit and interprets the rest of the input as some "non-silly" universal language (Ruby, in their case).
Kolmogorov Complexity normally tries to ignore the particular choice of language (since, in principle, any turing-complete language can emulate any other with a constant (but probably large) overhead). Their point is that language choice matters a lot, since there's nothing to prevent us choosing a universal language which just-so-happens to favour some outputs much more than others.
I get what they're saying, but there are solutions to this, in particular minimal languages like Binary Lambda Calculus, Binary Combinatory Logic, Wolfram's 2/3 turing machine, the rule 110 cellular automaton, Brainfuck, etc.
These are akin to "nothing up my sleeve numbers" used in cryptography (where the choice of parameter is pretty much arbitrary, but technically there are certain "silly" choices that would undermine the security)
For some interesting applications one might look at the the Wikipedia article for the normalized compression distance: https://en.wikipedia.org/wiki/Normalized_compression_distanc...
This paper here shows some interesting applications - it is not the first one, but the first non-paywalled one that I found: https://arxiv.org/pdf/cs/0312044.pdf
There is also a book by Paul Vitanyi - it has been a while since I looked at it, but if I remember correctly it also discusses some of these applications: https://www.amazon.com/Introduction-Kolmogorov-Complexity-Ap...