[4][6] By 2005, he held the position of Professor II at Rutgers, reserved for those faculty who have achieved scholarly eminence in their discipline.

[6] Khachiyan is best known for his four-page February 1979 paper[12] that indicated how an ellipsoid method for linear programming can be implemented in polynomial time.

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.

[15][9][13] 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.

"[18] 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.

"[19] Michael Todd, another colleague, described him as "cynical about politics," "very modest and kind to his friends," and "intolerant of condescension and pomposity.

[6][23] "Computer scientists and mathematicians say his work helped revolutionize his field," noted his New York Times obituary.

[4] 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.