Leonid KhachiyanFriday, April 5, 2019
A Soviet mathematician of Armenian descent who taught Computer Science at Rutgers University. 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.
Prior to moving to the United States in 1989, Khachiyan held a series of research and teaching positions at the Computing Center of the USSR Academy of Sciences and the Moscow Institute of Physics and Technology. In 1989 he joined Cornell University’s School of Operations Research and Industrial Engineering as a visiting professor and had been at Rutgers since 1990.
After moving to the United States, Khachiyan's work continued some of its old ideas, as he worked on the complexity of maximal volume inscribed ellipsoids and wrote a paper on rounding polytopes, adding some new ones. He wrote a series of papers with Bahman Kalantari on various matrix scaling and balancing problems.
Khachiyan is survived by his wife of 20 years and two daughters who currently live in the United States. He is also survived by his father, a retired professor of theoretical mechanics, his mother, a retired civil engineer, and two brothers, all of whom live in Moscow.