MacArthur Fellows Program

MacArthur Fellows / Meet the Class of 2012

Maria Chudnovsky


Associate Professor, Department of Industrial Engineering and Operations Research

Columbia University

New York, New York

Age: 35 at time of award

Published October 2, 2012

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.


High-resolution photos for download. 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.

For More Information


What's New

"Dinner Party Mathematics" thumbnail

"Dinner Party Mathematics"

Princeton University
Maria Chudnovsky, 2012 MacArthur Fellow
Read More
"Perfect Graphs and Perfect Harmony: Meet 2 of the 2012 MacArthur "Genius" Fellows" thumbnail

"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
Read More
23 MacArthur Fellows Announced thumbnail

23 MacArthur Fellows Announced

MacArthur named 23 new MacArthur Fellows for 2012. Working across a broad spectrum of endeavors, the Fellows include a pediatric neurosurgeon, a marine ecologist, a journalist, a photographer, an optical physicist and astronomer, a stringed-instrument bow ... Read More