Revisiting “The Great Mathematical Sputnik of 1979”

The news regarding Leonid Khachiyan’s polynomial time algorithm for linear programming (LP), published in a Soviet journal in February 1979, took many months to reach the scientific community in the West. When it was finally made public in October 1979, The Guardian and The New York Times wrote controversial stories about it, providing misleading information on the impact of Khachiyan’s discovery. 

This led the late Eugene Lawler from UC Berkeley, a key figure in disseminating the news to U.S.-based researchers, to write a piece titled “The Great Mathematical Sputnik of 1979.”¹ The article was published in The Mathematical Intelligencer in December 1980, where Lawler shared his personal recollections as well as his candid impressions of these events. An earlier version of this piece appeared in The Sciences in September 1980.² Here we revisit these fascinating accounts.

Khachiyan’s famous four-page paper demonstrated how an ellipsoid method for LP could be implemented in polynomial time. It was received on October 4, 1978, and published, without proofs, in February 1979 in Doklady Akademii Nauk SSSR, remaining largely unknown in the West until it was discovered a few months later.³

Breakthrough Reaches the West

In May 1979, Lawler was attending a conference in Oberwolfach, Germany. He recalls that EURO Gold Medalist Rainer Burkard shared with those present a “very blurry Xerox copy of a Russian paper that had been mailed to him a few days before by a friend at the Polish Academy of Sciences in Warsaw.”

Someone there could read Russian and explained what the paper was about. A few days later, Lawler loosely translated the paper into English with the help of Milan Vlach, a Czech mathematician who knew Russian. Lawler sent copies to about a dozen colleagues in the U.S., hoping someone would do the “dog work,” as he put it, of verifying whether the reported results were indeed correct.

Lawler did not hear back from anyone until July 1979, when Hungarian mathematicians Péter Gács and László Lovász, who were visiting Stanford University at the time, examined the paper and were able to prove the results. Lovász reportedly said that it took them a couple of days to complete this “medium-hard” task.⁴ 

These findings were then shared with about 300 people during a special session at the 10th ISMP conference in Montréal on August, 30, 1975, as reported by Phil Wolfe in an article on the ellipsoid method published in the very first issue of OPTIMA.^5-6 Gács and Lovász submitted their results for publication in October 1979, and the paper was published in 1981.⁷ Another paper on the topic was published by Bengt Aspvall and Richard E. Stone in 1980 in the very first issue of Journal of Algorithms.⁸

Khachiyan himself published a paper that contained the missing proofs from his earlier work in Russian in the January-February 1980 issue of USSR Computational Mathematics and Mathematical Physics.⁹ The paper was received by the journal on December 12, 1978, and the revised version arrived on August 13, 1979. 

In early October 1979, Lynn Arthur Steen, an American mathematician, published an article about Khachiyan’s findings that drew public attention to the work of the then-obscure Soviet mathematician. According to Lawler, “despite some inaccurate and misleading illustrations, the account was generally correct and did not seriously misstate the significance of the achievement.”¹⁰

On November 2, 1979, the article, “Mathematicians Amazed by Russian’s Discovery” by Gina Bari Kolata appeared in Science magazine.⁴ While preparing it, Kolata spoke with several distinguished researchers, including Lawler himself, Lovász, Robert Bland (known for the famous Bland’s rule for preventing cycles in the simplex algorithm), and the late Ronald Graham. 

The article also included an interesting quote from George Dantzig: “A lot of people, including myself, spent a lot of time looking for a polynomial time algorithm for linear programming. I feel stupid that I didn’t see it.” Lawler said the article “was generally accurate and well balanced.”

Misleading Statements

However, Kolata’s article also contained one particularly fuzzy passage connecting Khachiyan’s result with the traveling salesman problem (TSP), a combinatorial optimization problem that cannot be directly solved using pure LP. By stating that famous mathematicians were “amazed by the Russian’s discovery [that] it is tied to what is said to be the major unsolved problem [TSP] in computer science,” Kolata inadvertently misled the mainstream press, which published sensationalist stories about it.

The Guardian promptly capitalized on this and published a misleading story entitled, “Russian Way with the Mathematical Travelling Salesman,” stating that Khachiyan had “found an answer to one of the most baffling problems in computer calculation,” erroneously implying that he had solved the TSP.¹¹ As Lawler later wrote, “The Guardian story, communicated by its Washington correspondent, appears to have been based on nothing more than a very careless misreading of the Science story.” 

It is worth noting that The Guardian article appeared on October 29, 1979, while the Science article was published on November 2, 1979. One may speculate that the Washington correspondent had access to the article prior to its official publication. Lawler also added that “The London Telegraph rewrite offered the observation that there are few traveling salesmen in Communist countries, a fact which the Chicago Tribune found worthy of editorial comment.” In any case, The Guardian article concluded with an accurate prediction: “The consensus of the mathematical fraternity is that the Russian’s obscurity is not 
likely to last if he continues to produce work of this calibre.”

On November 7, 1979, a story by Malcolm W. Browne entitled, “A Soviet Discovery Rocks World of Mathematics” broke on the front page of The New York Times.¹² The article stated, “The Russian discovery proposes an approach for using computers to solve a kind of problem related to the ‘Traveling Salesman Problem,’ one of the most famous and intractable in mathematics.” Browne then went further, linking the TSP with an application associated with coding theory, adding that, “The theory of codes could eventually be affected by the Russian discovery, and this fact has obvious importance to intelligence organizations everywhere.” 

Lawler’s reaction to this alarmist narrative was priceless: “One could almost hear alarm bells ringing in the offices of the CIA and NSA.”

But Browne was not the only one who saw Khachiyan’s discovery as a potential threat to the U.S. government and national security. Poor Dantzig told Browne in an interview that he had “been deluged with calls from virtually every department of government for an interpretation of the significance of this.” Furthermore, Browne wrote in the story that “Dr. Dantzig said that in the last few days the university was inundated by requests for the paper.” 

Dantzig was not the only “victim.” Lawler, Gács, and Graham were also contacted by many curious people eager to learn more about the Russian discovery. As Lawler recalls, “A Beverly Hills lawyer asked if this new development might affect the immigration status of a client,” and Graham “was called by a radio talk show host and asked if it wasn’t true that the Russian discovery would change the lives of every man, woman, and child in America.” Lawler was even asked by Time Magazine whether Khachiyan deserved a cover story as the “Man of the Year.”

Khachiyan Arrives in the West

While Khachiyan never made it to the cover of Time magazine, The New York Times published another story about him on November 27, 1979, written by Craig R. Whitney, suggesting that Khachiyan was no longer an obscure Soviet mathematician.¹³ The story suggests that Khachiyan was “somewhat surprised” by the repercussions of his paper in the West. It also portrays him as a simple, down-to-earth character, depicting him as a “relaxed, friendly young man in a sweater who speaks a little English, which he learned in high school.”

Khachiyan described himself as a “theoretical mathematician … just working on a class of very difficult mathematical problems.” Whitney ended the story with an amusing quote from Khachiyan: “I tried to take up karate as a hobby about three years ago, but now I do mathematics instead.”

The New York Times did end up publishing a debatable retraction on March 21, 1980.¹⁴ Unfortunately, the narrative is misleading, because it subtly shifts responsibility for the original exaggeration from the newspapers to Khachiyan himself, creating the false impression that he overstated his work rather than being misrepresented by the press. The timeline of events revolving around Kachiyan's algorithm is depicted in Figure 1.

Dantzig and Khachiyan finally met in February of 1990, exactly eleven years after the publication of Khachiyan’s paper (see Fig. 2). The meeting took place in Asilomar, California, in a workshop on interior point methods organized by SIAM called “Progress in Mathematical Programming.”

Khachiyan moved to the U.S. in 1989. After spending time as a visiting professor at Cornell University, he joined Rutgers University, where he worked until his premature death on April 29, 2005, at age 52. Dantzig died less than a month later at age 90 on May 13, 2005. In a matter of weeks, the world lost two LP giants.

I only wish Khachiyan were still alive so I could have had the chance to interview him on my “Subject to (s.t.)” podcast and learn more about these and other anecdotes.¹⁵ Based on accounts by Michael Todd, Vašek Chvátal, and Bahman Kalantari, I am sure he would have been a wonderful guest.^16-18

 References

1. Lawler, E. L., 1980, “The Great Mathematical Sputnik of 1979,” The Mathematical Intelligencer, Vol. 2, pp. 191–198.
2. Lawler, E. L., 1980, “The Great Mathematical Sputnik of 1979,” The Sciences, Vol. 20, No. 7, pp. 12–15.
3. Khachiyan, L. G., 1979, “A Polynomial Algorithm in Linear Programming,” Doklady Akademii Nauk SSSR (Proceedings of the USSR Academy of Sciences), Vol. 244, pp. 1093-1096.
4. Kolata, G. B., 1979, “Mathematicians Amazed by Russian’s Discovery,” Science, Vol. 206, No. 4418, pp. 545-546.
5. Program of the 10th ISMP Conference, 1976. https://www.math.uwaterloo.ca/~bico/ismp/ismp1979_program.pdf
6. Wolfe, P., 1980, “The Ellipsoid Algorithm,” OPTIMA, Vol. 1. https://mathopt.zib.de/Old-Optima-Issues/optima1.pdf.
7. Gács, P., Lovász, L., 1981, “Khachiyan’s Algorithm for Linear Programming,” Mathematical Programming at Oberwolfach, König, H., Korte, B.. Ritter, K. (eds.), pp. 61-68, Springer, Berlin, Heidelberg.
8. Aspvall, B., Stone, R. E., 1980, “Khachiyan’s Linear Programming Algorithm,” Journal of Algorithms, Vol. 1, No. 1, pp. 1–13.
9. Khachiyan, L. G., 1980, “Polynomial Algorithms in Linear Programming,” Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki (USSR Computational Mathematics and Mathematical Physics), Vol. 20, pp. 51–68.
10. Steen, L. A., 1979, “Linear Programming: Solid New Algorithm,” Science News, Vol. 116, No. 14, pp. 234–236.
11. “Russian Way with the Mathematical Travelling Salesman,” 1979. The Guardian, Oct. 29.
12. Browne, M. W., 1979, “A Soviet Discovery Rocks World of Mathematics,” The New York Times, Nov. 7.
13. Whitney, C. R., 1979, “Soviet Mathematician Is Obscure No More,” The New York Times, Nov. 27.
14. “A Russian’s Solution in Math Questioned,” 1980, The New York Times, Mar. 21.
15. “Subject to (s.t.),” YouTube, https://www.youtube.com/@Subjectto_/videos.
16. Todd, M. J., 2005, “Leonid Khachiyan, 1952–2005: An Appreciation,” SIAG/OPT Views-and-News, Vol. 16, Nos. 1-2.
17. Chvátal, V., 2008, “Remembering Leo Khachiyan,” Discrete Applied Mathematics, Vol. 156, No. 11, pp. 1961–1962.
18. Kalantari, B., My Memories of Leonid Khachiyan and a Personal Tribute for His Contributions in Linear Programming,, https://web.archive.org/web/20200113214307/https://pdfs.semanticscholar.org/da18/7ecf2133060ec3fd96e0b2588885e4eae262.pdf.