Blair Sullivan, professeure invitée du LIP

Biographie

Titulaire d'un doctorat en mathématiques de Princeton et d'une licence de Georgia Tech, Blair D. Sullivan est professeure d'informatique à l'Université de l'Utah. Auparavant, elle a occupé des postes à l'Université d'État de Caroline du Nord et au Laboratoire national d'Oak Ridge. Elle travaille plus particulièrement sur le thème « Rapprocher théorie et pratique : améliorer l'utilisabilité des algorithmes paramétrés pour l'analyse de réseaux via la modification de largeurs jumelles et de graphes ».

Collaboration avec le LIP

L’équipe MC2 du LIP, composée notamment d’Édouard Bonnet, Stéphan Thomassé et Rémi Watrigant, a introduit la notion de twin-width, une mesure de complexité des graphes. Ce concept a eu un impact majeur dans la communauté scientifique, comme en témoignent la médaille de bronze du CNRS d’Édouard Bonnet et les nombreuses citations de leur article publié dans le Journal of the ACM en 2021. La chercheuse Blair Sullivan, spécialiste du calcul effectif de twin-width, partage un fort intérêt pour les applications pratiques de l’algorithmique des graphes. Ainsi, une collaboration entre son équipe et le LIP promet des avancées conjointes, à la fois théoriques et appliquées. Cette synergie pourra faire émerger de nouvelles questions et ouvrir des perspectives inédites de recherche.

Par ailleurs, une coopération est envisagée avec l’équipe Roma, dirigée par Bora Uçar, autour du partitionnement d’hypergraphes. Ce domaine est crucial pour des applications comme le calcul haute performance, la conception de circuits VLSI et les réseaux de neurones graphiques. Les chercheurs cherchent à améliorer les outils de partitionnement en modifiant la structure des hypergraphes. En ce sens, Bora Uçar et ses collègues ont déjà développé des heuristiques rapides pour certaines classes d’hypergraphes. L’expertise de Blair Sullivan en édition de graphes et d’hypergraphes sera donc particulièrement utile dans ce contexte.

D'autre part, les chercheurs du LIP entretiennent déjà des liens étroits avec l’équipe GOAL du LIRIS. Ils partagent un séminaire commun (Graphe@Lyon) et de nombreuses publications conjointes et les travaux de Blair Sullivan sur l’édition de graphes les intéressent. Cette nouvelle collaboration renforcera encore les échanges entre les équipes lyonnaises en théorie des graphes.

Publications majeures

• M. Bentert, A. Crane, D. Coimbra Salomao†, Y. Mizutani, F. Reidl, B. D. Sullivan. A Space-Efficient Algebraic Approach to Robotic Motion Planning. Under conference review (Feb 2025). ArXiv:2409.08219
• M. Pividori, S. Lu, B. Li, C. Su, M. E. Johnson, W. Wei, Q. Feng, B. Namjou, K. Kiryluk, I. Kullo, Y. Luo, B. D. Sullivan, B. F. Voight, C. Skarke, M. Ritchie, S. Grant, C. S. Greene. Projecting genetic associations through gene expression patterns highlights disease etiology and drug mechanisms. Nature Communication 14, 2023. bioRxiv:2021.07.05.450786.
• M. Breen-McKay, B. Lavallee, B. D. Sullivan. Hardness of the Generalized Coloring Numbers. ArXiv:2112.10562. European J. of Combinatorics 123:103709, 2025.
• Y. Mizutani, D. Dursteler, B. D. Sullivan. Hydra Prime: An Exact Solver for Twin-width. Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC) 2023.