English
Derandomization, tutorial - part 1: Pseudo-randomness from hardness
Multi angle
Auteurs : Kabanets, Valentine (Auteur de la conférence)
CIRM (Editeur )
68Q15 - Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 - Computational difficulty of problems
68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/3151/Slides/kabanets-slides_19-20_feb.pdf
CIRM (Editeur )
Loading the player...
|
Résumé :
Mots-Clés : pseudorandomness; derandomization; computational complexity; circuit complexity; Kolmogorov complexity; meta-complexity
Codes MSC : 68Q15 - Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 - Computational difficulty of problems
68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/3151/Slides/kabanets-slides_19-20_feb.pdf
|
Informations sur la Vidéo
Réalisateur : Recanzone, LucaLangue : Anglais Date de Publication : 11/03/2024 Date de Captation : 19/02/2024 Sous Collection : Research School Catégorie arXiv : Computational Complexity Domaine(s) : Informatique Format : MP4 (.mp4) - HD Durée : 01:14:33 Audience : Chercheurs ; Etudiants Science Cycle 2 ; Doctoral Students, Post-Doctoral Students ; Etudiants Download : https://videos.cirm-math.fr/2024-02-19_Kabanets_1_2.mp4 
|
Informations sur la Rencontre
Nom de la Rencontre : Randomness, Information & Complexity / Aléatoire, information et complexité - Week 4Organisateurs de la Rencontre : Bienvenu, Laurent ; Perifel, Sylvain ; Romashchenko, Andrei ; Shen, Alexander ; Theyssier, Guillaume Dates : 19/02/2024 - 23/02/2024 Année de la rencontre : 2024 URL de la Rencontre : https://conferences.cirm-math.fr/3151.html
Données de citation
DOI : 10.24350/CIRM.V.20141203Citer cette vidéo: Kabanets, Valentine (2024). Derandomization, tutorial - part 1: Pseudo-randomness from hardness. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.20141203 URI : http://dx.doi.org/10.24350/CIRM.V.20141203 |
Voir Aussi
- [Multi angle] Tutorial 3: Pseudodeterministic constructions and $rK^{t}$ / Auteur de la conférence Carboni Oliveira, Igor.
- [Multi angle] Derandomization, tutorial - part 2: Meta-complexity / Auteur de la conférence Kabanets, Valentine.
- [Multi angle] Tutorial 2: Complexity theory through the lens of Kolmogorov complexity / Auteur de la conférence Carboni Oliveira, Igor.
- [Multi angle] Tutorial 1: Probabilistic notions of Kolmogorov complexity / Auteur de la conférence Carboni Oliveira, Igor.
Bibliographie
Imagette Video
