Maria Chudnovsky (born January 6, 1977) is an

Israel Israel (; he, יִשְׂרָאֵל, ; ar, إِسْرَائِيل, ), officially the State of Israel ( he, מְדִינַת יִשְׂרָאֵל, label=none, translit=Medīnat Yīsrāʾēl; ), is a country in Western Asia. It is situated ...

American American(s) may refer to: * American, something of, from, or related to the United States of America, commonly known as the "United States" or "America" ** Americans, citizens and nationals of the United States of America ** American ancestry, pe ...

mathematician working on

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

and

combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...

. She is a 2012 MacArthur Fellow.

Education and career

Chudnovsky is a professor in the department of mathematics at

Princeton University Princeton University is a private university, private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial Colleges, fourth-oldest ins ...

. She grew up in

Russia Russia (, , ), or the Russian Federation, is a List of transcontinental countries, transcontinental country spanning Eastern Europe and North Asia, Northern Asia. It is the List of countries and dependencies by area, largest country in the ...

(attended

Saint Petersburg Lyceum 30 {{Infobox school , name = Physico-Mathematical Lyceum 30 , native_name = Физико-математический лицей №30 , logo = , image = , image_size = , alt = ...

) and

, studying at the Technion, and received her Ph.D. in 2003 from

under the supervision of Paul Seymour. After postdoctoral research at the

Clay Mathematics Institute The Clay Mathematics Institute (CMI) is a private, non-profit foundation (nonprofit), foundation dedicated to increasing and disseminating mathematics, mathematical knowledge. Formerly based in Peterborough, New Hampshire, the corporate address i ...

,. she became an assistant professor at Princeton University in 2005, and moved to

Columbia University Columbia University (also known as Columbia, and officially as Columbia University in the City of New York) is a private research university in New York City. Established in 1754 as King's College on the grounds of Trinity Church in Manhatt ...

in 2006. By 2014, she was the Liu Family Professor of Industrial Engineering and Operations Research at Columbia. She returned to Princeton as a professor of mathematics in 2015.

Research

Chudnovsky's contributions to

include the proof of the strong perfect graph theorem (with

Neil Robertson Neil Robertson (born 11 February 1982) is an Australian professional snooker player who is a former world champion and former world number one. The only Australian to have won a ranking event, he is also the only player from outside the United ...

, Paul Seymour, and

Robin Thomas Robin may refer to: Animals * Australasian robins, red-breasted songbirds of the family Petroicidae * Many members of the subfamily Saxicolinae (Old World chats), including: **European robin (''Erithacus rubecula'') ** Bush-robin **Forest ro ...

) characterizing

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfec ...

s as being exactly the graphs with no odd

induced Induce may refer to: * Induced consumption * Induced innovation * Induced character * Induced coma * Induced menopause * Induced metric * Induced path * Induced topology * Induce (musician), American musician See also * Inducement (disambiguation ...

cycles of length at least 5 or their complements. Other research contributions of Chudnovsky include co-authorship of the first

polynomial-time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

algorithm for recognizing perfect graphs (time bounded by a polynomial of degree 9), and of a structural characterization of the

claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph ''K''1,3 (that is, a star graph comprising three edges, three leaves, ...

Selected publications

*. *. *. *

Awards and honors

In 2004 Chudnovsky was named one of the "Brilliant 10" by

Popular Science magazine ''Popular Science'' (also known as ''PopSci'') is an American digital magazine carrying popular science content, which refers to articles for the general reader on science and technology subjects. ''Popular Science'' has won over 58 awards, inclu ...

. Her work on the strong perfect graph theorem won for her and her co-authors the 2009

Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...

. In 2012 she was awarded a "genius award" under the

MacArthur Fellows Program The MacArthur Fellows Program, also known as the MacArthur Fellowship and commonly but unofficially known as the "Genius Grant", is a prize awarded annually by the John D. and Catherine T. MacArthur Foundation typically to between 20 and 30 ind ...

Personal life

She is a citizen of Israel and a permanent resident of the US. In 2012, she married Daniel Panner, a viola player who teaches at

Mannes School of Music Mannes School of Music is a music conservatory in The New School, a private research university in New York City. In the fall of 2015, Mannes moved from its previous location on Manhattan's Upper West Side to join the rest of the New School cam ...

and the

Juilliard School The Juilliard School ( ) is a private performing arts conservatory in New York City. Established in 1905, the school trains about 850 undergraduate and graduate students in dance, drama, and music. It is widely regarded as one of the most el ...

. They have a son named Rafael.

References

External links

Chudnovsky's home page at Princeton University
{{DEFAULTSORT:Chudnovsky, Maria Living people Graph theorists Princeton University alumni Princeton University faculty Columbia University faculty Israeli mathematicians Women mathematicians 1977 births MacArthur Fellows Combinatorialists