In 1979, at the height of the Cold War, a seven-page paper written by an unknown Russian mathematician was presented at the International Mathematical Programming Symposium in Montreal. American mathematicians were impressed with the paper: "The Polynomial Algorithm in Linear Programming" by L.G. Khachiyan. Washington was in a panic.
Michael Grigoriadis, a professor of computer science at Rutgers, was working with IBM in 1979. "The revelation in Montreal turned the NSA (National Security Agency) upside down," he said. Grigoriadis recalled how the CEO of IBM pressed his mathematicians for explanations of this new theory.
A Page One story in The New York Times labeled the Khachiyan paper "the mathematical Sputnik," referring to the Russians launching a satellite in 1957 Mb a shocking victory over the American rocket scientists.
Over time, the unknown Russian, said Grigoriadis, "opened up the field to thousands of papers."
Leonid G. Khachiyan would immigrate to the United States in 1989, and one year later he joined the Rutgers faculty. "We were striking gold," Grigoriadis said of the hiring.
On Friday, Khachiyan, a resident of South Brunswick, died of a heart attack, four days before his 53rd birthday. Computer science lost a pioneer. Grigoriadis lost a friend.
It is hard for the layman to appreciate Khachiyan's work. (I did manage a D in freshman calculus.)
According to Grigoriadis, linear programming had been around for decades. What Khachiyan did was introduce a theory, showing how to solve linear programming problems thought impossible at the time. He was a pioneer in what is known as "combinatorial optimization," that is, finding the best solution to problems with billions of variables.
Combinatorial optimization is how airlines make schedules, automakers assemble cars, oil producers produce their product, and McDonald's delivers french fries.
"Fifty years from now, one hundred years from now, if there are three people who are going to be remembered for combinatorial optimization, Khachiyan will be one of them," said Rutgers computer science Professor Bahman Kalantari, a graduate student at the University of Minnesota in 1979, who recalls the fuss over the unknown Russian's work.
In 1989 Grigoriadis and Kalantari met Khachiyan at a conference at Cornell University. When Khachiyan was recruited by Rutgers, Kalantari gave him a choice of staying in a hotel or sleeping on a spare bed at Kalantari's apartment on Easton Avenue.
"He chose to come to my apartment," said Kalantari, "and we talked math all night."
And who wouldn't have liked to have been a fly on that wall?
Mathematicians like Grigoriadis, Kalantari and Khachiyan live in a fascinating universe. It was in this universe mathematicians developed theories that would lead to creation of the Internet. Of its creators, Grigoriadis said, "We know them and they are not the (Bill) Gates." Mathematicians do the numbers and theories, while the marketing geniuses make the big bucks.
This summer you will book an airline flight, reserve a hotel room and pick up a copy of USA Today, produced by companies that do work more efficiently because of combinatorial optimization. Thanks in part to the work of Leonid Khachiyan.
Rick Malwitz's column appears
Sundays and Thursdays. Call (732)565-7291; e-mail rmalwitz@thnt.com.