Chuzhoy Held Banner
Julia Chuzhoy, Toyota Technological Institute at Chicago, received the 2020 Michael and Sheila Held Prize.
Chuzhoy has conducted influential work in the fields of graph algorithms, hardness of approximation, and structural graph theory, which have introduced powerful new techniques and resolved deep open questions.
Chuzhoy and her co-authors achieved remarkable results in designing algorithms for graph routing problems, which are among the most-studied and important problems in optimization. Insights from this work led to further significant impacts on structural graph theory, including an exponential strengthening of the parameters of Excluded Grid theorem.
Chuzhoy’s work on graph routing problems settled central open questions in graph optimization and introduced powerful new graph decomposition and routing techniques, opening up the potential for future applications in algorithm design and structural graph theory. The improved parameters for the Excluded grid theorem led to faster algorithms for a host of graph optimization problems, and stronger bounds for a number of graph theoretic results.
The Michael and Sheila Held Prize is presented annually and carries with it a $100,000 prize. The prize honors outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. This $100,000 prize is intended to recognize recent work (defined as published within the last eight years). The prize was established in 2017 by the bequest of Michael and Sheila Held.
