-
Recherche
- Présentation
- Trimestres et mois thématiques
- Evénements scientifiques
-
Chercheurs invités
- Chercheurs invités 2021
- Chercheurs invités 2022
- Chercheurs invités 2023
-
Post-doctorants Milyon
- Post-doctorants 2022
- Post-doctorants 2023
- Publications
- Prix, honneurs, bourses de recherche
- Portraits de chercheurs
- Formation
- Médiation
- Entreprise
- Appels à candidature
- Contacts
Vous êtes ici : Version française > Présentation > Thèses
-
Partager cette page
Thèse soutenue
Publié le 18 janvier 2021 | Mis à jour le 9 mars 2023
Asymptotic properties of hypergraphs and channels
Ta Duy-Hoang
Thèse sous la direction de : Omar Fawzi, LIP, ENS de Lyon Discipline : Informatique
Lire la thèse
Comprendre les propriétés des objets dans le cadre d'une opération de produit naturel est un thème central en mathématiques, en informatique et en physique. Des exemples de tels objets de base incluent les canaux de communication bruyants en théorie de l'information, les problèmes de calcul en complexité algébrique et les graphes en mathématiques discrètes. Dans cette thèse, nous étudions la croissance asymptotique de propriétés pertinentes pour les puissances de tels objets. Les premiers objets que nous considérons sont des hypergraphes munis de l'opération de produit fort et la propriété d'intérêt est le nombre d'indépendance. La croissance asymptotique du nombre d'indépendance d'un hypergraphe est connue sous le nom de capacité de Shannon. Nous introduisons une méthode générale pour minorer la capacité de Shannon des hypergraphes via des dégénérescences combinatoires, une notion issue de l'étude de la multiplication matricielle en théorie de la complexité algébrique. Cela nous permet d'obtenir les bornes inférieures les plus connues pour de multiples problèmes combinatoires, y compris le problème du coin et son application dans la complexité de la communication. Les tenseurs sont les seconds objets considérés. Nous pouvons les équiper du produit tensoriel et la propriété d'intérêt est le sous-rang symétrique. Le sous-rang symétrique est une notion que nous introduisons motivée par les limitations des méthodes de tenseur actuelles pour borner la capacité de Shannon des hypergraphes. Nous prouvons des relations et séparations précises entre sous-rang et sous-rang symétrique. Nous prouvons également que pour les tenseurs symétriques, le sous-rang et le sous-rang symétrique sont asymptotiquement égaux. Cela prouve l'analogue de sous-rang asymptotique d'une conjecture connue sous le nom de conjecture de Comon dans la théorie des tenseurs. Enfin, nous étudions la croissance de la divergence entre les puissances tensorielles des canaux quantiques. En exploitant les symétries, nous proposons des algorithmes efficaces pour approximer la divergence asymptotique des canaux entre canaux. Comme application, nous obtenons des bornes améliorées sur les capacités des canaux quantiques.