Français
Tutorial 2: Complexity theory through the lens of Kolmogorov complexity
Multi angle
Authors : Carboni Oliveira, Igor (Author of the conference)
CIRM (Publisher )
68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
Additional resources :
https://www.cirm-math.fr/RepOrga/3151/Slides/oliveira-slides2.pdf
CIRM (Publisher )
Loading the player...
|
Abstract :
Keywords : Kolmogorov complexity; meta-complexity; randomised algorithms
MSC Codes : 68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
Additional resources :
https://www.cirm-math.fr/RepOrga/3151/Slides/oliveira-slides2.pdf
|
Information on the Video
Film maker : Recanzone, LucaLanguage : English Available date : 11/03/2024 Conference Date : 20/02/2024 Subseries : Research School arXiv category : Computational Complexity ; Information Theory Mathematical Area(s) : Computer Science ; Logic and Foundations Format : MP4 (.mp4) - HD Video Time : 01:00:03 Targeted Audience : Researchers ; Graduate Students ; Doctoral Students, Post-Doctoral Students Download : https://videos.cirm-math.fr/2024-02-20_Oliveira_part2.mp4 
|
Information on the Event
Event Title : Randomness, Information & Complexity / Aléatoire, information et complexité - Week 4Event Organizers : Bienvenu, Laurent ; Perifel, Sylvain ; Romashchenko, Andrei ; Shen, Alexander ; Theyssier, Guillaume Dates : 19/02/2024 - 23/02/2024 Event Year : 2024 Event URL : https://conferences.cirm-math.fr/3151.html
Citation Data
DOI : 10.24350/CIRM.V.20141303Cite this video as: Carboni Oliveira, Igor (2024). Tutorial 2: Complexity theory through the lens of Kolmogorov complexity. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.20141303 URI : http://dx.doi.org/10.24350/CIRM.V.20141303 |
See Also
- [Multi angle] Tutorial 3: Pseudodeterministic constructions and $rK^{t}$ / Author of the conference Carboni Oliveira, Igor.
- [Multi angle] Derandomization, tutorial - part 2: Meta-complexity / Author of the conference Kabanets, Valentine.
- [Multi angle] Derandomization, tutorial - part 1: Pseudo-randomness from hardness / Author of the conference Kabanets, Valentine.
- [Multi angle] Tutorial 1: Probabilistic notions of Kolmogorov complexity / Author of the conference Carboni Oliveira, Igor.
Bibliography
- HIRAHARA, Shuichi, ILANGO, Rahul, LU, Zhenjian, et al. A duality between one-way functions and average-case symmetry of information. In : Proceedings of the STOC 2023: 55th Annual ACM Symposium on Theory of Computing. ACM, 2023. - http://wrap.warwick.ac.uk/174719
Imagette Video
