Topics in Kolmogorov Complexity, Seminar 236804

Kolmogorov, Andrey Nikolayevich

Instructor:

Ran El-Yaniv
Office: 526, Phone: 829-4328, Email: rani@cs.technion.ac.il
Office hours: Monday 16:30-17:30
Lecture hour: Sunday 12:30-14:30, Taub 8

Kolgmogorov complexity is a deep and sophisticated theory that provides the means to measure the intrinsic information in objects via their algorithmic description length. It applies to a wide range of areas including theory of computation, combinatorics, inductive reasoning and machine learning. In this seminar we will cover the basics and some applications of Kolmogorov complexity. The main text for this seminar will be An introduction to Kolmogorov complexity and its applications by Li and Vitanyi.

Requirements:

each student is required to give an individual presentation, submit a short article summarizing his/her presentation, read all the seminar articles and background material, and is expected to attend all the classes and contribute to the discussions. All these components will contribute to the seminar?s final mark. Specifically, to get a full mark, students have to successfully complete the following tasks:

Reading: All students are required to read all relevant lecture material before attending the lectures. At least a week before each presentation the presenting student is responsible to distribute all relevant material to his/her talk.
Summary paper: One week prior to his/her presentation each student should submit a detailed summary of his/her presentation. Although there will be several intersecting or overlapping presentations, the summary paper should be individual. The abstract should be printed and be no longer than four pages. It should summarize and outline the presentation and should address and
answer the following issues:
- What is the main subject of the presentation;
- what kind of techniques are used;
- What is the significance of the presented results;
- relation to previous presentations;
- a detailed outline of the presentation.
Distribution of presentation material: At least one week before the presentation the lecturer is responsible to distribute to the seminar members a photocopy of the presentation material and his/her summary paper. Students can obtain from me a photocopying card for this purpose.
Presentations and presentation slides: Presentations should be held using high quality printed slides in either Hebrew or English. As a rule of thumb, each individual presentation should be no longer than 40 slides.

Attendance and participation:

Each student is expected to attend all seminar meetings, be involved in other students? presentations, read other students? presentation summaries, and participate in the discussions.

The Lecture program:

All section references in the list below are to the course book: An Introduction to Kolmogorov Complexity and its applications, by Li and Vitanyi, Second edition.

Number	Topic and slides (when available)	Lecturer	Date	Section in the book
0	Overview	Ran El-Yaniv	.	.
1	Introduction as PPT, as PS	Asaf Mesika	.	1.1, 1.2, 1.4, 1.6, 1.7, 1.11
2	Algorithmic complexity	Shimon Landa	.	2.1, 2.2, 2.3
3,4	Algorithmic complexity lecture sum, as PS, slides	Eitan Joshua	.	2.4, 2.5, 2.6, 2.8
5	Algorithmic prefix complexity, lecture sum and slides	Yariv Maron	30/4	3.1 - 3.5
6	Algorithmic probability, lecture sum 1, 2, 3 lecture slides	Shiri Moran	7/5	4.1, 4.2, 4.3
7	Algorithmic probability	Vitali Feldman	14/5	4.5
8	Inductive reasoning, slides , word doc	Tzach Livyatan	21/5	5.1, 5.2 5.3
9	Inductive reasoning	Davidov Dmitry	4/6	5.4
10	Physics, Information and Computation	Dmitry Gavinsky	11/6	8
11	Inductive reasoning	Philip Derbeko	18/6	5.5
12	Physics, Information and Computation, as PDF, as PPT	Ziv Nevo	25/6	8

Topics in Kolmogorov Complexity, Seminar 236804

Kolmogorov, Andrey Nikolayevich

Instructor:

Requirements:

Attendance and participation:

The Lecture program:

Number

Topic and slides (when available)

Lecturer

Date

Section in the book

Related links: