Julia Chuzhoy

Julia Chuzhoy obtient son B.A. en 1998, son mastère en 2000, puis son doctorat en 2004 au Technion, l'Institut de Technologie Israélien[1]. Sa thèse, intitulée « Hardness of Approximation and New Approximability Classes », porte sur les algorithmes d'approximation et elle a été supervisée par Joseph Seffi Naor (en)[2].

Après son doctorat elle travaille trois ans au Massachusetts Institute of Technology auprès de Piotr Indyk et Madhu Sudan, à l'Université de Pennsylvanie auprès de Sanjeev Khanna et à l' Institute for Advanced Study auprès d'Avi Wigderson.

Elle travaille comme Associate Professor au Toyota Technological Institute at Chicago (en)[1] depuis 2007 et elle occupe en même temps un poste au Département d'Informatique de l'Université de Chicago[3].

Chuzhoy a remporté le prix du meilleur article lors de l'édition 2012 du Symposium on Foundations of Computer Science, colloque sur les fondations de l'informatique, pour son article avec Shi Li sur l'approximation du problème de la connexion de nombreuses paires données de sommets dans un graphe par des chemins en arêtes disjointes[4] - [5] - [6].

Elle est également connue pour son travail en montrant une relation polynômiale entre la taille d'un graphe grille mineur d'un graphe et sa largeur arborescente[7] - [8]. Cette connexion entre ces deux propriétés d'un graphe est un composant clé du théorème de Robertson-Seymour, et c'est étroitement relié au théorème de la grille de Halin (en) pour des graphes infinis, et sous-tend la théorie de la bidimensionalité (en) pour les algorithmes d'approximation de graphes.

Julia Chuzhoy est conférencière invitée en 2014 au congrès international des mathématiciens à Séoul, avec une conférence intitulée « Cuts and Integral Routing in Graphs, an Approximation Algorithmist's Perspective »[9] - [3]. En 2011 elle est titulaire d'une bourse Sloan et en 2009 elle reçoit un NSF Career Award. Elle est lauréate du prix Michael et Sheila Held en 2020.

• (en) Julia Chuzhoy et Shi Li, « A polylogarithimic approximation algorithm for edge-disjoint paths with congestion », dans 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science—FOCS 2012, IEEE Computer Soc., Los Alamitos, CA, 2012 (MR 3186610), p. 233–242.

• Chandra Chekuri et Julia Chuzhoy, « Polynomial bounds for the grid-minor theorem », Journal of the ACM, vol. 63, n^o 5,‎ 2016, A40:1–65 (DOI 10.1145/2820609, MR 3593966, arXiv 1305.6577). Des versions préliminaires de ce travail ont été présentés lors des éditions 2014 et 2015 des Symposia on Theory of Computing.

• page personnelle sur le site de l'université de Chicago
• Publications sur Google Scholar.