MacArthur Fellows Program

Maria Chudnovsky

Mathematician | Class of 2012

Investigating the fundamental principles of graph theory and laying the conceptual foundations for deepening connections between graph theory and other major branches of mathematics, such as linear programming and geometry.

Title
Mathematician
Affiliation
Columbia University
Location
New York, New York
Age
35 at time of award

Maria Chudnovsky is a mathematician who investigates the fundamental principles of graph theory. In mathematics, a graph is an abstraction that represents a set of similar things and the connections between them—e.g., cities and the roads connecting them, networks of friendship among people, web sites and their links to other sites. When used to solve real-world problems, like efficient scheduling for an airline or package delivery service, graphs are usually so complex that it is not possible to determine whether testing all the possibilities individually will find the best solution in a practical time period. Chudnovsky explores classifications and properties of graphs that can serve as shortcuts to brute-force methods; showing that a specific graph belongs to a certain class often implies that it can be calculated relatively quickly. In an early breakthrough, Chudnovsky and colleagues proved a conjecture offered in the early 1960s, known as the “Strong Perfect Graph Theorem,” that identifies specific criteria required for a graph to fall into the “perfect” class. Any perfect graph can be colored efficiently (i.e., no node is connected to another node of the same color), and graph coloring bears a direct relation to finding efficient solutions to problems such as allocating non-interfering radio frequencies in communication networks. Since this landmark accomplishment, Chudnovsky has continued to generate a series of important results in graph theory. Although her research is highly abstract, she is laying the conceptual foundations for deepening the connections between graph theory and other major branches of mathematics, such as linear programming, geometry, and complexity theory.  

Maria Chudnovsky received B.A. (1996) and M.Sc. (1999) degrees from Technion, Israel Institute of Technology, and an M.A. (2002) and a Ph.D. (2003) from Princeton University. She was affiliated with Princeton University (2003–2006) and a research fellow at the Clay Mathematics Institute (2003–2008) prior to joining the faculty of Columbia University, where she is currently an associate professor in the Department of Industrial Engineering and Operations Research, with a courtesy appointment in the Department of Mathematics.

News About this Fellow
January 7, 2016
"Dinner Party Mathematics"
Princeton University
Maria Chudnovsky, 2012 MacArthur Fellow
October 5, 2012
"Perfect Graphs and Perfect Harmony: Meet 2 of the 2012 MacArthur "Genius" Fellows"
From Scientific American
2012 MacArthur Fellows: Maria Chudnovsky and BenoƮt Rolland
View all news

Photos

Photos are owned by the MacArthur Foundation and licensed under a Creative Commons license: CC-BY.
Credit: John D. & Catherine T. MacArthur Foundation.

Right-click on a link below to save the file to your computer.


More Fellows

View All 2012 Fellows

Stay Informed
Sign up for periodic news updates and event invitations. Connect with us on Twitter, Facebook, and YouTube.