MacArthur Fellows Program

MacArthur Fellows / Meet the Class of 2012

Maria Chudnovsky

Mathematician

Associate Professor, Department of Industrial Engineering and Operations Research

Columbia University

New York, NY

Age: 35

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.

Photos

Hi-res photos for download. Photos licensed under a Creative Commons license. Courtesy of the John D. & Catherine T. MacArthur Foundation. Right-click on the links below to save the file to your computer.

Maria Chudnovsky In the Media

"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

About the Fellows Program

The MacArthur Fellows Program awards unrestricted fellowships to talented individuals who have shown extraordinary originality and dedication in their creative pursuits and a marked capacity for self-direction. Learn More

Jeffrey Brenner, Primary Care Physician

Class of 2013

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