Kolmogorov complexity fall2025 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
Brbauwens (обсуждение | вклад) |
Brbauwens (обсуждение | вклад) |
||
| (не показано 40 промежуточных версии этого же участника) | |||
| Строка 2: | Строка 2: | ||
= Classes = | = Classes = | ||
| − | Lectures + seminar: Friday 18h10 -- 21h00 in Pokrovkaya room | + | Lectures + seminar: Friday 18h10 -- 21h00 in Pokrovkaya, the room is on line 20 [https://docs.google.com/spreadsheets/d/1nrzlctbhbJ6sBk0DGq_RZz-P2Tk3Ocu9mXyP6UzzgOo/edit?gid=0#gid=0 here] and in [https://us02web.zoom.us/j/82300259484?pwd=NWxXekxBeE5yMm9UTmwvLzNNNGlnUT09 zoom]. The teacher is [https://www.hse.ru/en/org/persons/160550073 Bruno Bauwens]. |
Telegram group for announcements and discussions [https://t.me/+DwgZDmhRORgxZjg0 invite link.] | Telegram group for announcements and discussions [https://t.me/+DwgZDmhRORgxZjg0 invite link.] | ||
| Строка 14: | Строка 14: | ||
! Rec !! Summary !! Notes !! Problem list !! Solutions | ! Rec !! Summary !! Notes !! Problem list !! Solutions | ||
|- | |- | ||
| − | || [https:// | + | || [https://rutube.ru/video/a7c6eee70cf19f9c3fa364e6421e3246 10.10] || Course overview, (universal) Turing machines, computable and non-computable sets and functions. [https://www.dropbox.com/scl/fi/0fxjeu8h1ekawcueto4yn/01slides.pdf?rlkey=ww3ec2ngtoysexwoc6wahcfg4&st=7t55t5bi&dl=0 slides.pdf] || [https://www.dropbox.com/scl/fi/n1vhfvtfagv2ji6x30exn/00notes.pdf?rlkey=pvd79gi91567mut35n87j1vfo&st=ypsaw36s&dl=0 ch00] [https://www.dropbox.com/scl/fi/cm2xfnegccktu3s7h00wy/01notes.pdf?rlkey=87ctjsio681ee821tzlomufqp&st=jvdlwdnn&dl=0 ch01]|| [https://www.dropbox.com/scl/fi/7qwg0cdxm41vp9awrr6iw/01sem.pdf?rlkey=ix23k6otcnc0ym2byrc4rgs1g&st=im58g130&dl=0 sem01] || [https://www.dropbox.com/scl/fi/ptqijcgwf70yfca3kcwxs/01sol.pdf?rlkey=7cchyt7p75bqylz75mj3ehg9n&st=ursmcybk&dl=0 sol01] |
|- | |- | ||
| − | + | || [https://youtube.com/live/gxtqX9ZhJfQ 17.10] || Plain Kolmogorov complexity, simple properties, upper bounds, symmetry of information (see also [https://arxiv.org/pdf/1504.04955 notes]) || [https://www.dropbox.com/scl/fi/4ujoo1ppjxyib8ehz66il/04slides.pdf?rlkey=gz6npiztww9fcui2pgktxp6pz&st=09bw895o&dl=0 05sl] || [https://www.dropbox.com/scl/fi/4it73pfmwjy1t7m2mqhkw/02sem.pdf?rlkey=qr5mt2mmqjot19vg8pmycs1ek&st=avpkd9qv&dl=0 sem02] upd 03.11 | |
| + | || [https://www.dropbox.com/scl/fi/o5fff9ikngnayzhefpxbz/02sol.pdf?rlkey=softuys65jaxhq70l77we9508&st=2s8v90ba&dl=0 sol02] | ||
|- | |- | ||
| − | || 25.10 || Minimizing loss according to unknown computable measure (non-responsive systems). Merhav-Feder and Helinger bounds for Bayesian mixtures. || [https://www.dropbox.com/scl/fi/isxpy6t5v9remzwlvt5e2/04notes.pdf?rlkey=gxhs69b00tcye4y8mmv4x5qyx&st=xalcy9a4&dl=0 ch04] || see notes ch04 || | + | || <!-- [https://www.youtube.com/watch?v=p6vKnnPfVOM 25.10]--> [https://rutube.ru/video/865c221a0b1d7431680b0236b6116a82/ 25.10] || Optimality of Solomonoff induction. See Vitanyi chapter 5.1--5.2 for background. [https://www.dropbox.com/scl/fi/rgdv6lhsjyauupmi319pw/02slides.pdf?rlkey=86etkg0bnbxx7debnvo5d8i2q&st=etj740r0&dl=0 slides.pdf]|| [https://www.dropbox.com/scl/fi/hhkk87q66ebx54vtswkge/02notes.pdf?rlkey=argdpb3l8ky75lj1g7n94175e&st=rqfszhit&dl=0 ch02] [https://www.dropbox.com/scl/fi/wjihhy6iuoxjuh9gje6b7/03notes.pdf?rlkey=03s29gprfjej7qwrvju8icaus&st=hlhvwri5&dl=0 ch03]|| [https://www.dropbox.com/scl/fi/x3chzhcrl3qzakuhyrik6/03sem.pdf?rlkey=mbcbobwn73fsj0a1e3c424x4a&st=qd9siz5a&dl=0 sem03] || [https://www.dropbox.com/scl/fi/maro4fk0h5fr2uvncf58g/03sol.pdf?rlkey=nevucf12rz3ywvwwp3f9sly3s&st=i8bcrhbd&dl=0 sol03] |
| + | <!-- |- | ||
| + | || 24.10 || Minimizing loss according to unknown computable measure (non-responsive systems). Merhav-Feder and Helinger bounds for Bayesian mixtures. || [https://www.dropbox.com/scl/fi/isxpy6t5v9remzwlvt5e2/04notes.pdf?rlkey=gxhs69b00tcye4y8mmv4x5qyx&st=xalcy9a4&dl=0 ch04] || see notes ch04 || --> | ||
|- | |- | ||
| − | || [https:// | + | || [https://drive.google.com/file/d/11rPr-3Z7BkEUZ9bGelnHX19QXC_SyW54/view?usp=sharing 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. || [https://www.dropbox.com/scl/fi/i97a1auk5x10aqomx6its/05notes.pdf?rlkey=kcmufbn1w70m48n4lvbp5yp54&st=rswmru4w&dl=0 ch05] || [https://www.dropbox.com/scl/fi/7ovfpljxe5p59vfhthzrk/04sem.pdf?rlkey=18urcicegj875oiu7x21sj2gi&st=p8nergg7&dl=0 sem04] |
|- | |- | ||
| − | || [https:// | + | || [https://drive.google.com/file/d/11rPr-3Z7BkEUZ9bGelnHX19QXC_SyW54/view?usp=drive_link 14.11] || Prefix Kolmogorov complexity 2 definitions. Precise symmetry of information (proof next time). || [https://www.dropbox.com/scl/fi/zu84z1smw9m0rdns54ohr/05slides.pdf?rlkey=fakwr6sbl3fadwbydsecsz4mb&st=nyuu4wmz&dl=0 06sl] || [https://www.dropbox.com/scl/fi/1a05vzsn449cnvycqxvmr/05sem.pdf?rlkey=re2kkl2cagxz9tqtos05liipv&st=gzuzg3sq&dl=0 sem05] || |
|- | |- | ||
| − | || [https:// | + | || [https://drive.google.com/file/d/1ulkswiIOvB-mxok_sUwffNzvw1Vy_4tf/view?usp=drive_link 21.11] || Algorithmic statistics [https://arxiv.org/pdf/1607.08077 overview paper]. Seminar: incompressibility method || [https://www.dropbox.com/scl/fi/h23o9y87rrybderjirri3/algStatNotes.pdf?rlkey=u2gq3vzfxy4xfo2q524keiyez&st=xe5pfn0c&dl=0 ch09] || [https://www.dropbox.com/scl/fi/zmb0hajmclre451fvvsnj/06sem.pdf?rlkey=becx5d4auwhgpjfaewatgmkej&st=4t3e0xzt&dl=0 sem06] || |
| + | <!--|- | ||
| + | || [https://youtube.com/live/o8GS-4fCACk 28.11] || Algorithmic statistics, (notes later) || || [https://www.dropbox.com/scl/fi/gap1istjpb9xe80nfu5mb/08sem.pdf?rlkey=blefd1fodq4x0zhommsnp0h6i&st=rzaqhybe&dl=0 sem08] || --> | ||
|- | |- | ||
| − | || [https:// | + | || [https://drive.google.com/file/d/10rYr0v8MRHO_ldiV3d1xYM6DXOAC_zEO/view?usp=drive_link 28.11] || Time bounded (decision) complexity, hash functions and language compression, P=NP implies symmetry of time-bounded complexity. || || [https://www.dropbox.com/scl/fi/3izk9t67v07rm4r354wnl/07sem.pdf?rlkey=rzd9slcmorkdy0n5bcd0kf3cv&st=edujzruy&dl=0 sem07] || |
| − | |- | + | |- |
| − | || | + | || 12.12 || Optional lecture: 1-way functions exist if and only if with symmetry of information holds for pK^t-complexity holds with high probability for poly time sampled x and y. From [https://wrap.warwick.ac.uk/id/eprint/174719/1/WRAP-A-duality-between-one-way-functions-and-average-case-symmetry-of-information-Oliveira-2023.pdf this] paper. || || || |
|- | |- | ||
| − | || | + | || 24.12 || 17h-20h Exam and colloquium. [https://www.dropbox.com/scl/fi/9bhuvect79u9pxnxmf87j/col.pdf?rlkey=pizqnk66a4vv0vcaypqg8nzyd&st=2vx46jm7&dl=0 questions and rules]. || || || |
|} | |} | ||
| Строка 38: | Строка 43: | ||
= Homeworks = | = 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 [https:// | + | 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 [https://docs.google.com/spreadsheets/d/1_vO5Q0wGkM0kU1OHNiP8lz24M4i-toLC2AmQg7tuRVE/edit?usp=sharing 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. | 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. | ||
| − | |||
| − | |||
| − | |||
| Строка 66: | Строка 68: | ||
= Office hours = | = Office hours = | ||
| − | Bruno Bauwens: Tuesday | + | Bruno Bauwens: Tuesday 15h -- 21h. Friday 15h -- 18h. Contact in telegram for other moments |
Текущая версия на 23:31, 6 декабря 2025
Содержание
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 | ch09 | sem06 | |
| 28.11 | Time bounded (decision) complexity, hash functions and language compression, P=NP implies symmetry of time-bounded complexity. | sem07 | ||
| 12.12 | Optional lecture: 1-way functions exist if and only if with symmetry of information holds for pK^t-complexity holds with high probability for poly time sampled x and y. From this paper. | |||
| 24.12 | 17h-20h Exam and colloquium. 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
