Kolmogorov complexity fall2025

Classes

Lectures + seminar: Friday 18h10 -- 21h00 in Pokrovkaya, the room is on line 20 here and in zoom. The teacher is Bruno Bauwens.

Telegram group for announcements and discussions invite link.

Course Materials

Rec	Summary	Notes	Problem list	Solutions
10.10	Course overview, (universal) Turing machines, computable and non-computable sets and functions. slides.pdf	ch00 ch01	sem01	sol01
17.10	Plain Kolmogorov complexity, simple properties, upper bounds, symmetry of information (see also notes)	05sl	sem02 upd 03.11	sol02
25.10	Optimality of Solomonoff induction. See Vitanyi chapter 5.1--5.2 for background. slides.pdf	ch02 ch03	sem03	sol03
07.11	Minimizing loss in responsive systems. Self-optimizing strategies in sets of environments. If there exists a self-optimizing strategy, then a Bayesian mixture over all environments in a countable set is self optimizing. A variant with algorithmic probability.	ch05	sem04
14.11	Prefix Kolmogorov complexity 2 definitions. Precise symmetry of information (proof next time).	06sl	sem05
21.11	Algorithmic statistics overview paper. Seminar: incompressibility method	07sl	sem06
28.11	Time bounded (decision) complexity, hash functions and language compression, P=NP implies symmetry of time-bounded complexity.		sem07
05.12	Optional lecture. 1-way functions exist if and only symmetry of information holds for pK^t-complexity, paper.
12.12	Colloquium. Previous year's questions and rules.

Homeworks

Deadlines: every 2 weeks, before the lecture at 18h00. Submit in pdf or fotos of handwritten to brbauwens@gmail.com with the subject line starting with KOLM-HW. Link with results will be here.

Tasks are in the problem lists from the seminar. Deadlines: problem lists 1 and 2: at the start of 3rd lecture, lists 3 and 4 at the start of the 5th lecture, etc.

References

See notes00.pdf above.

Grading

Final score = 0.35 * [score homework] + 0.35 * [score colloquium] + 0.3 * [score exam] 

Some homework assignments contain extra problems. Each solution of an extra problem will give 1 extra points on the final exam (which is graded out of 10). There will be around 10 extra problems. Rounding is applied only when the final score is transferred to the official grade. Arithmetic rounding is used. Autogrades. If only 6/10 for the exam is needed to get a final score of 10/10, then this will be given automatically.

Colloquium and exam

Colloquium: in the middel of December, a list with about 10 questions will be provided.

Exam: Problems similar to the homework. You may use main references, lecture notes, and handwritten notes.

Office hours

Bruno Bauwens: Tuesday 15h -- 21h. Friday 15h -- 18h. Contact in telegram for other moments