Leonid KhachiyanWednesday, May 5, 2021
Leonid Genrikhovich Khachiyan (May 3, 1952 – April 29, 2005) was a Soviet and American mathematician and computer scientist.
He was most famous for his ellipsoid algorithm (1979) for linear programming, which was the first such algorithm known to have a polynomial running time. Even though this algorithm was shown to be impractical due to the high degree of the polynomial in its running time, it has inspired other randomized algorithms for convex programming and is considered a significant theoretical breakthrough.
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. His grandparents were Karabakh Armenians. He had two brothers: Boris and Yevgeniy (Eugene). His family moved to Moscow in 1961, when he was nine. He received a master's degree from the Moscow Institute of Physics and Technology. 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.
Khachiyan began his career at the Soviet Academy of Sciences, working as a researcher at the Academy's Computer Center in Moscow. He also worked as an adjunct professor at the Moscow Institute of Physics and Technology. In 1979 he stated: "I am a theoretical mathematician and I'm just working on a class of very difficult mathematical problems." Khachiyan immigrated to the United States in 1989. He first taught at Cornell University as a visiting professor. In 1990 he joined Rutgers University as a visiting professor. He became professor of computer science at Rutgers in 1992. By 2005, he held the position of Professor II at Rutgers.
Khachiyan spoke Russian and English, but not Armenian. Bahman Kalantari noted that "For some, his English accent wasn’t always easy to understand." The 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."
He was known as "Leo" and "Lenya" to his friends and colleagues. Václav Chvátal described him as "selfless, open, patient, sympathetic, understanding, considerate." Michael Todd, another colleague, described him as "cynical about politics," "very modest and kind to his friends," and "intolerant of condescension and pomposity."
Khachiyan married Olga Pischikova Reynberg, of Russian-Jewish origin, in 1985. They had two daughters, Anna and Nina, who were teenagers at the time of his death. He became a naturalized U.S. citizen in 2000. He died of a heart attack in South Brunswick, New Jersey on April 29, 2005, at the age of 52.