---

Manuscrit de thèse

---

Résumé

Les données de grande dimension sont courantes dans des domaines tels que la génomique, le traitement d'images et l'analyse des réseaux sociaux. Elles posent des défis importants en matière d'analyse computationnelle et statistique. L'augmentation de la taille des ensembles de données dans ces différents domaines accroît le besoin d'outils efficaces d'approximation des données. Même si la dimension des données peut être grande, leur dimension intrinsèque, c’est-à-dire la dimension minimale de l’information qu’elles contiennent, peut être réduite. Cela est représenté à travers des concepts tels que la dimension VC, que nous discutons dans ce travail. Nous concentrons notre étude sur la recherche d’algorithmes efficaces pour de grands ensembles de données de dimension intrinsèque fixe.

Dans cette thèse, nous présentons des algorithmes pour calculer des structures fondamentales de la réduction combinatoire des données : \(\varepsilon\)-approximations, \(\delta\)-recouvrements, colorations à faible discrépance et partitions à faibles croisements. En particulier, nous étudions les trois problèmes suivants.

Dans la première partie, nous présentons un nouveau jeu à deux joueurs et montrons l'existence d'une stratégie quasi-optimale en utilisant le célèbre algorithme de discrépance de Lovett-Meka. Nous présentons ensuite un algorithme à poids multiplicatifs pour calculer une famille de colorations à faible discrépance moyenne, utilisant la valeur de notre jeu dans son analyse.

Dans la deuxième partie, nous présentons un nouvel algorithme de partition à faibles croisements pour les systèmes d'ensembles généraux. Il s'agit de la première instance d'un algorithme pratiquement rapide pour calculer des partitions à faibles croisements de systèmes d'ensembles généraux, les résultats précédents utilisant étant limités aux systèmes engendrés par des demi-espaces en dimension faible.

Enfin, nous présentons de nouveaux algorithmes pour calculer des \(\delta\)-recouvrements quasi minimaux de systèmes d'ensembles de dimension VC finie. Ces algorithmes sont les premiers algorithmes non triviaux permettant d'obtenir des \(\delta\)-recouvrements de taille minimale. Nous en présentons des applications à la coloration à faible discrépance et à l'\(\varepsilon\)-approximation, en dérivant des algorithmes plus rapides atteignant la discrépance optimale pour les systèmes d'ensembles de dimension VC finie : \(O(n^{1 / 2-1 / (2d)})\).

Manuscrit

Repose sur les publications suivantes

• A New Discrepancy Game with Victor-Emmanuel Brunel and Nabil Mustafa. https://hal.science/hal-05064760 [pdf]

• A Greedy Algorithm for Low-Crossing Partitions for General Set Systems with Mónika Csikós and Nabil Mustafa. In 2025 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) (pp. 209-220). Society for Industrial and Applied Mathematics. [pdf]

Autres publications

• Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers with Sujoy Bhore, Balázs Keszegh, Andrey Kupavskii, Hung Le, Dömötör Pálvölgyi, and Csaba D. Tóth. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 4292-4326). Society for Industrial and Applied Mathematics. [pdf]

Jury