Maria Chudnovsky

About Maria's Work

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.  

Biography

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.