Leonid Khachiyan

Leonid Genrikhovich Khachiyan<ref name="Nytobscure79"/>Template:Efn (Template:IPAc-en;<ref name="NYT2005"/> Template:Langx; May 3, 1952Template:Spaced ndashApril 29, 2005) was a Soviet and American mathematician and computer scientist.

He was most famous for his ellipsoid algorithm (1979) for linear programming,<ref>Template:Cite journal</ref> which was the first such algorithm known to have a polynomial running time. Even though this algorithm was shown to be impractical, it has inspired other randomized algorithms for convex programming and is considered a significant theoretical breakthrough.

Early life and education

Khachiyan was born on May 3, 1952, in Leningrad to Armenian parents Genrikh Borisovich Khachiyan, a mathematician and professor of theoretical mechanics, and Zhanna Saakovna Khachiyan, a civil engineer.<ref name="rutgers"/><ref name="Nytobscure79"/> His grandparents were Karabakh Armenians.<ref name="Gurvich"/><ref>Template:Cite web</ref> He had two brothers: Boris and Yevgeniy (Eugene).<ref name="rutgers"/><ref name="NYT2005"/> His family moved to Moscow in 1961, when he was nine.<ref name="Nytobscure79"/><ref name="rutgers"/> He received a master's degree from the Moscow Institute of Physics and Technology.<ref name="NYT2005"/> In 1978 he earned his Ph.D. in computational mathematics/theoretical mathematics from the Computer Center of the Soviet Academy of Sciences and in 1984 a D.Sc. in computer science from the same institution.<ref name="rutgers"/><ref name="NYT2005"/><ref name="Nytobscure79"/>

Career

Khachiyan began his career at the Soviet Academy of Sciences,<ref name="NYT2005"/> working as a researcher at the academy's Computer Center in Moscow.<ref name="Nytobscure79"/> He also worked as an adjunct professor at the Moscow Institute of Physics and Technology.<ref name="SIAMTodd"/> In 1979 he stated: "I am a theoretical mathematician and I'm just working on a class of very difficult mathematical problems."<ref name="Nytobscure79"/> Khachiyan immigrated to the United States in 1989.<ref name="latimes"/><ref name="rutgers"/> He first taught at Cornell University as a visiting professor. In 1990 he joined Rutgers University as a visiting professor.<ref name="NYT2005"/><ref name="rutgers"/><ref name="SIAMTodd"/> He became professor<ref name="MIT"/> of computer science at Rutgers in 1992.<ref name="NYT2005"/><ref name="rutgers"/> By 2005, he held the position of Professor II at Rutgers, reserved for those faculty who have achieved scholarly eminence in their discipline.<ref name="rutgers"/>

Work on linear programming

Ellipsoid method

Khachiyan is best known for his four-page February 1979 paper<ref>Khachiyan, L. G. 1979. "A Polynomial Algorithm in Linear Programming". Doklady Akademii Nauk SSSR 244, 1093-1096 (translated in Soviet Mathematics Doklady 20, 191-194, 1979).</ref> that indicated how an ellipsoid method for linear programming can be implemented in polynomial time.<ref name="1981survey"/><ref name="SIAMTodd"/> The paper was translated into several languages and spread around the world unusually quickly. Authors of a 1981 survey of his work noted that it "has caused great excitement and stimulated a flood of technical papers" and was covered by major newspapers.<ref name="1981survey"/> It was originally published without proofs, which were provided by Khachiyan in a later paper published in 1980<ref>Khachiyan, L. G. 1980. "Polynomial Algorithms in Linear Programming". Zhurnal Vychisditel'noi Matematiki i Matematicheskoi Fiziki (USSR Computational Mathematics and Mathematical Physics) 20, 51-68.</ref> and by Peter Gács and Laszlo Lovász in 1981.<ref>Template:Cite book</ref><ref name="SIAMTodd"/><ref name="1981survey"/> It was Gács and Lovász who first brought attention to Khachiyan's paper at the International Symposium on Mathematical Programming in Montreal in August 1979.<ref name="1981survey"/><ref name="rutgers"/> It was further popularized when Gina Kolata reported it in Science Magazine on November 2, 1979.<ref>Template:Cite journal</ref><ref name="MIT"/>

Khachiyan's theory is considered a groundbreaking one that "helped advance the field of linear programming."<ref name="MIT"/> Giorgio Ausiello noted that the method was not practical, "but it was a real breakthrough for the world of operations research and computer science, since it proved that the design of polynomial time algorithms for linear programming was possible and in fact opened the way to other, more practical, algorithms that were designed in the following years."<ref>Template:Cite book</ref>

Personal life and death

Khachiyan spoke Russian and English, but not Armenian.<ref name="Gurvich"/> Bahman Kalantari noted that "For some, his English accent wasn’t always easy to understand."<ref name="Kalantari"/> A 1979 New York Times profile of him described Khachiyan as "a relaxed, friendly young man in a sweater who speaks a little English, which he learned in high school."<ref name="Nytobscure79"/>

He was known as "Leo"<ref name="Gurvich"/><ref name="Chvátal"/> and "Lenya" to his friends and colleagues.<ref name="SiamOrgTodd"/> Václav Chvátal described him as "selfless, open, patient, sympathetic, understanding, considerate."<ref name="Chvátal"/> Michael Todd, another colleague, described him as "cynical about politics," "very modest and kind to his friends," and "intolerant of condescension and pomposity."<ref name="SIAMTodd"/>

Khachiyan married Olga Pischikova Reynberg, of Russian-Jewish origin,<ref>Template:Cite web</ref> in 1985.<ref name="rutgers"/><ref name="SIAMTodd"/> They had two daughters, Anna and Nina,<ref name="rutgers"/><ref name="NYT2005"/> who were teenagers at the time of his death.<ref name="SIAMTodd"/> He became a naturalized U.S. citizen in 2000.<ref name="NYT2005"/><ref name="MIT"/> He died of a heart attack in South Brunswick, New Jersey on April 29, 2005, at the age of 52.<ref name="NYT2005"/><ref name="rutgers"/><ref name="MIT"/>

Recognition

In 1982 he was awarded the prestigious Fulkerson Prize by the Mathematical Programming Society and the American Mathematical Society<ref name="latimes"/> for outstanding papers in the area of discrete mathematics,<ref name="rutgers"/> particularly his 1979 article "A polynomial algorithm in linear programming."<ref>Template:Cite web</ref>

Khachiyan was considered a "noted expert in computer science whose work helped computers process extremely complex problems."<ref name="latimes"/> He was called one of the world's most famous computer scientists at the time of his death by Haym Hirsh, chair of the computer science department at Rutgers.<ref name="rutgers"/><ref name="boston"/> "Computer scientists and mathematicians say his work helped revolutionize his field," noted his New York Times obituary.<ref name="NYT2005"/> Bahman Kalantari, a friend and colleague at Rutgers, wrote: "Surely, Khachiyan shall always remain to be among the greatest and most legendary figures in the field of mathematical programming."<ref name="Kalantari"/>

References

Notes

Citations

External links

• DBLP: Leonid Khachiyan.
• In Memoriam: Leonid Khachiyan from the Computer Science Department, Rutgers University.
• SIAM news: Leonid Khachiyan, 1952–2005: An Appreciation.
• Discrete Applied Mathematics: Remembering Leo Khachiyan
• The Mathematics Genealogy Project: Leonid Khachiyan.
• New York Times : Obituary.

Template:Authority control