<p>I'm a private math tutor who also tutors some theoretical CS.  Last semester I had a student who needed tutoring in Kolmogorov Complexity.  I told her that I only know <em>about</em> Kolmogorov Complexity, but had no detailed knowledge of it, and she should find a tutor who did know it.  She said that she was completely unable to find such a tutor.  So I agreed to help ... and read some online material about K.C.</p>
<p>I was able to help her to <em>some</em> extent -- the basic concept, some simple results.  But the homework gave some very precise upper limits to the K.C. of some specific strings (or string patterns) and asked for proofs of those limits.</p>
<p>I assume the limits came from finding <em>some</em> algorithm to generate the strings, and then characterizing the algorithm.  But for most of them, I could not come up with such an algorithm.  I tried &quot;reverse engineering&quot; the answers, to get some hint of the algorithms ... with no success.</p>
<p>The class is over, and the student got an A.  (K.C. was only a small part of the course, and I was able to help her on at least part of it.)  The student said that there was never an answer handout for those problems.  I quite likely might never receive a request to tutor this again ... but for my own satisfaction I would love to know how those limits were derived.</p>
<p>Can anyone recommend an online course or article that shows examples of coming up with such detailed and precise upper limits for K.C.?  I prefer to do that, rather than simply post the problems and ask for an answer.  Thanks!</p>

CC BY-SA 4.0
2022-01-17T04:02:03.390Z
I'm pretty sure the `online-learning` tag is meant for the machine learning concept, not online education, based on the other questions under that tag.
Jake
CC BY-SA 4.0
2022-01-17T11:22:18.217Z
You probably know the standard textbook *An introduction to Kolmogorov complexity and its applications* by  Li & Vitanyi, I doubt there is a dedicated MOOC on KC, it's too niche a topic (alas). Trivial KC upper bound for any string $s$ is something like `print(s)`, expressed as the ambient programming model lets you. Better upper bounds can be found using standard lossless compression tricks like used in `zip` and other compression tools, eg. [run-length encoding](https://en.wikipedia.org/wiki/Run-length_encoding).
Martin Berger
CC BY-SA 4.0
2022-02-02T11:57:40.810Z
Jake, thanks for the clarification to a newbie.

Martin, thanks for the information.
Dudley Brooks
<kolmogorov-complexity><online-learning>
Online *detailed* tutorials about Komogorov Complexity
Dudley Brooks
# Online *detailed* tutorials about Komogorov Complexity

(Asked by: username_0 on 2022-01-16)

I'm a private math tutor who also tutors some theoretical CS. Last semester I had a student who needed tutoring in Kolmogorov Complexity. I told her that I only know *about* Kolmogorov Complexity, but had no detailed knowledge of it, and she should find a tutor who did know it. She said that she was completely unable to find such a tutor. So I agreed to help ... and read some online material about K.C.

I was able to help her to *some* extent -- the basic concept, some simple results. But the homework gave some very precise upper limits to the K.C. of some specific strings (or string patterns) and asked for proofs of those limits.

I assume the limits came from finding *some* algorithm to generate the strings, and then characterizing the algorithm. But for most of them, I could not come up with such an algorithm. I tried "reverse engineering" the answers, to get some hint of the algorithms ... with no success.

The class is over, and the student got an A. (K.C. was only a small part of the course, and I was able to help her on at least part of it.) The student said that there was never an answer handout for those problems. I quite likely might never receive a request to tutor this again ... but for my own satisfaction I would love to know how those limits were derived.

Can anyone recommend an online course or article that shows examples of coming up with such detailed and precise upper limits for K.C.? I prefer to do that, rather than simply post the problems and ask for an answer. Thanks!

**Tags:** kolmogorov-complexity, online-learning

> **Comments:**
> **username_1**: I'm pretty sure the `online-learning` tag is meant for the machine learning concept, not online education, based on the other questions under that tag.  
> **username_2**: You probably know the standard textbook *An introduction to Kolmogorov complexity and its applications* by  Li & Vitanyi, I doubt there is a dedicated MOOC on KC, it's too niche a topic (alas). Trivial KC upper bound for any string $s$ is something like `print(s)`, expressed as the ambient programming model lets you. Better upper bounds can be found using standard lossless compression tricks like used in `zip` and other compression tools, eg. [run-length encoding](https://en.wikipedia.org/wiki/Run-length_encoding).  
> **username_0**: username_1, thanks for the clarification to a newbie.  Martin, thanks for the information.  

---

## 0 answers

