HDR Sylvain Perifel Manuscript in pdf Slides in pdf [approx. 30MB] [English version below] La soutenance de mon habilitation à diriger des recherches aura lieu le lundi 4 décembre 2023 à 14h dans l'amphithéâtre Pierre-Gilles de Gennes du bâtiment Condorcet situé au 4 rue Elsa Morante, 75013 Paris. La soutenance se déroulera en anglais. La collation qui suivra se tiendra à l'IRIF (4e étage du bâtiment Sophie Germain, 8 place Aurélie Nemours, 75013 Paris) vers 17h probablement, et chacun y est le bienvenu. Titre : L'aléatoire par le prisme des polynômes et de la compression Jury : - Claire Mathieu, présidente, directrice de recherche au CNRS, Académie des sciences - Meena Mahajan, rapporteuse, professeure à l'Institut des sciences mathématiques de Chennai - Santiago Figueira, rapporteur, professeur à l'université de Buenos Aires - Olivier Bournez, rapporteur, professeur à l'École polytechnique - Damiano Mazza, examinateur, directeur de recherche au CNRS - Olivier Carton, examinateur, professeur à l'université Paris Cité, IUF « Résumé opérationnel » : Dans une première partie, nous comparerons quelques méthodes efficaces de compression (automates à pile, LZ'78, espace polylogarithmique), puis nous étudierons la « catastrophe du premier bit » pour l'algorithme de Lempel-Ziv, où l'ajout d'un seul bit peut changer le taux de compression. La seconde partie traitera de complexité algébrique, en particulier de bornes inférieures pour certains modèles de calcul de polynômes, et du célèbre problème de test d'identité polynomiale qui résiste encore aux tentatives de dérandomisation. The defence of my habilitation thesis will take place on Monday, December 4, 2023 at 2pm in the Pierre-Gilles de Gennes amphitheatre of the Condorcet building (4 rue Elsa Morante, 75013 Paris). The presentation will be given in English, and everyone is welcome to the refreshments that will follow at IRIF (4th floor, Sophie Germain building, 8 place Aurélie Nemours, 75013 Paris). Title: Randomness Through the Lens of Polynomials and Compression Jury: - Claire Mathieu, president, directrice de recherche au CNRS, Académie des sciences - Meena Mahajan, reviewer, professor at Institute of Mathematical Sciences of Chennai - Santiago Figueira, reviewer, professor at the university of Buenos Aires - Olivier Bournez, reviewer, professor at École polytechnique - Damiano Mazza, examiner, directeur de recherche au CNRS - Olivier Carton, examiner, professor at the university Paris Cité, IUF “Executive summary”: In the first part, we will compare some efficient compression methods (pushdown automata, LZ'78, polylogarithmic space), and study the “one-bit catastrophe” for Lempel-Ziv algorithm, where adding a single bit can change the compression ratio. The second part will deal with algebraic complexity, in particular lower bounds for certain models of computation of polynomials, and the famous polynomial identity test which still resists attempts of derandomisation.