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 Recipient
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 for Download

High-resolution photos of MacArthur Fellows are available for download (right click and save), including use by media, in accordance with this copyright policy.


Please credit: John D. & Catherine T. MacArthur Foundation

More Fellows

View All 2012 Fellows

Stay Informed
Sign up for periodic news updates and event invitations.
Check out our social media content in one place, or connect with us on Twitter, Facebook, YouTube, and LinkedIn.