A Note on Kolmogorov Complexity and Shannon Entropy

Links to the material: report.

This summary is what I have written for my course project in CS3236 Introduction to Information Theory during AY22/23 Sem 2. This is my first time writing stuffs this long in LaTex other than my maths assignments (say, those for the notoriously difficult MA2101S Linear Algebra II (S)). I burnt for many days without studying anything else to understand those materials, which was quite fun.

In general, I get to learn about Turing machines, how it is used to quantify complexity, and how this Kolmogorov complexity is related to a seemingly different notion of Shannon entropy taught in the class. This motivated me to take CS3231 Theory of Computation in the following academic year, which also turned out to be rewarding.

Remark. One particularly painful memory was that some sources do not clearly state whether they are using the self-delimiting version of Kolmogorov complexity, which confused me when different results are presented from different sources. Sometime I have to modify statements and corresponding proofs for one version to make it true for another version. On another note, I did not pay much attention to the writing and disrupted the flow by using too many footnotes. This is a habit I adapted from writing my math assignments, where the emphasis is on correctness and rigor rather than on readability, as long as the grader can discern the main ideas and logic. I tried to fix this issue in my latter writings.

The next time I saw the notion of Kolmogorov complexity was quite recent, in this paper on KeOps where the author claims that KeOps essentially leverages the low Kolmogorov complexity of symbolic arrays to achieve smaller runtime and memory usage for certain types of computation. The KeOps library might be very useful in my ongoing FYP where I need to train a full exact Gaussian process (GP) model and conduct Lanczos estimation based on it during test time: when I have 100k data, matrix-vector multiplication with the Gram matrix requiring way more GPU memory if using PyTorch only, and are only made available for me with the help of KeOps.