The Speed of Communication

Fifty years of acceleration

src

Kurt Gödel has been keeping a low profile recently. It’s not in his nature to distract from all of the celebrations of Alan Turing these past months, especially when he never met the man. Plus he can only communicate via time-traveling neutrinos, which CERN explained last February do not exist—the exciting superluminal measurements were artifacts of a loose cable. That dried up our funding before we could transcribe the second part of our interview, though as a result of this post we may have found an anonymous donor. It is hard to show continued progress when your working setup has been proved theoretically impossible, but that doesn’t stop cryptanalysts and it won’t stop us.

Today we present a communication to Gödel that he obtained by simpler means, and reflect on changes in research communication over just half a century—rather, a quarter-century.

The Rare Books and Special Collections department of Princeton’s Firestone Library has many boxes of Kurt Gödel’s correspondence and other writing and memorabilia. Most of the rest is in Vienna. One can in fact browse the catalog of Firestone’s Gödel holdings online, in commendably copious detail.

I (Ken) had the pleasure of looking through just a small portion of these materials while visiting Princeton in February. Here is my transcription of a letter by mathematician Willaim Boone of UIUC to Gödel on May 18, 1959, telling him of developments by Pyotr Novikov on William Burnside’s conjecture, which we covered last November, including also work on it by Marshall Hall, Jr. Also named are Warren Hirsch, whose conjecture we have also covered, John Thompson whom we mentioned here, and Andrzej Mostowski.

1959: News By Surface Letter

Bill Boone to Kurt Gödel, May 18, 1959—I did not note down the exact salutation, and it is not allowed to make photocopies of materials except by special permission.

Just wanted to tell you the big news that Novikov has settled the Burnside problem. (He so wrote Hirsch, who wrote Marshall Hall, Jr., who wrote a young man named Thompson at Chicago U., who wrote me!) Novikov says that the free group on two generators with the condition added that the Nth power of each element equals the identity, N ≥ 72, is ALWAYS an infinite group.

I have written Hirsch for details & will write Novikov shortly.

It would seem doubtful to me now that at this late date I could manage to get to the Warsaw meeting—however, I’ve written to John Addison to find out if it is a closed meeting. If it is not, I’ll write Mostowski directly—hopefully while he is still in the States.

Boone ended his letter by talking about some papers on the word problem for groups that he was reviewing.

Another letter from Boone was addressed “Dear Professor” and included a greeting to “Mrs. Gödel” with the umlaut hand-written in. He then gave the timeless plaint that “… my only trouble these days is that I seem so busy with classes that it is a struggle to get adequate time for research.” His very next sentence got to the point: “Given an arbitrary recursively enumerable degree of unsolvability…”

Of course, many scientific journals began by organizing the earlier system of private letters among members of research societies, and some even retain the word “Letters” in their title.

Whoops, Make that 1968

The details that Boone wrote for, alas, took almost a decade to arrive. If this mathematical announcement was like a promissory note, then the owed value after 9 years’ maturity can be said to have mushroomed from to in 1968. According to this history,

Novikov’s argument of 1959 was correct in general terms but the details were not, and in putting the arguments right it was found that one required larger values of N.

The fix required the help of his colleague Sergei Adian, and as we quote from Wikipedia’s biography of Adian, took more than Novikov to make the appeal:

…the concrete realization of [Novikov’s] ideas encountered serious difficulties, and in 1960, at the insistence of Novikov and his wife Lyudmila Keldysh, Adian settled down to work on the Burnside problem. Completing the project took intensive efforts from both collaborators in the course of eight years.

Another decade later Novikov and Adian paid it down to N = 665, and as we related here, it has come down to N = 115. Actually all these are resolutions only among odd exponents—for even exponents the going rate is N = = 281,474,976,710,656, but only among exponents that are multiples of 512. Adian also found a tragic one-line error in a 300-page attempted proof by John Britton.

Incidentally, Adian was later the PhD advisor of Alexander Razborov.

1984: Still Nothing Orwellian

E-mail was still unknown to me at Oxford in 1984—I recently told a story about being slow to communicate some research by surface mail. Only a few universities subscribed to the ARPANET, which is considered to have been the main precursor to the Internet. I did not use e-mail or newsgroups until starting a postdoc at Cornell in October 1986. Thus halfway through our 50-year period things were much the same.

1989: Interactive Proof Frenzy

The complexity characterization of interactive proofs was a landmark not only for complexity theory but also for the research use of e-mail. What the New York Times called a frenzy of e-mails not only communicated results about but led to the optimal form . One of the spurs was Seinosuke Toda’s proof the year before that the polynomial hierarchy reduces to counting, which I learned the spring before meeting him at the Structure in Complexity 1989 conference in Eugene, Oregon.

László Babai tells much of the story in his article “E-mail and the Unexpected Power of Interaction,” as does Ryan O’Donnell in his class notes, “A history of the PCP Theorem” drawing from Babai. The communications began on Nov. 27, 1989, when Noam Nisan announced to a few friends that the permanent has a multiple-prover interactive proof. Among them Lance Fortnow started a line of inquiry on getting this down to a single prover. He announced on Dec. 13, 1989 the breakthrough—mostly by Carsten Lund as first author and joint with him, Howard Karloff, and Nisan—showing that the polynomial hierarchy is contained in . The attached draft paper—until then mostly a local Chicago product—gave the first interactive protocol essentially using a non-constant number of rounds. About the ensuing race to improve the result, Babai writes:

I don’t know how many people began feverishly working on this problem with the keen sense that there would be just one winner: the one who first announces the (hopeful) result on e-mail.

That announcement would instantly kill all the competition. There are indications that a dozen may be a modest underestimate. Of the losers of the race, only those who achieved worthwhile by-products revealed themselves publicly.

The announcement came 13 days later, from Adi Shamir eight time zones away in Israel. This led to some hard feelings in Chicago, and Babai discusses some of the attendant ethical issues arising from both the scope of the group given the information and the speed of the medium.

Although such elite groups belong to the very nature of the hierarchy of scientific research (and the elites in question are among the most tolerant and open bunches in history…), their sheer intellectual force combined with the information advantage makes them look from outside like an impenetrable fortress. Among those who did not receive any of the mailings were Toda, Razborov, all of East Europe, …

Nor I. I learned about this after New Year’s, and about further developments later from my wife, an English teacher. She learned about them from her college roommate, a lawyer. Who soon married the Chicago theorist and former MIT office-mate of Lance’s she’d heard them from. But if blogs and/or arXiv had existed then, Lance might have communicated the draft that way, and the whole world would have been equal. Co-incidentally someone whose work on testing for the permanent is noted by both Babai and O’Donnell as partly instigating Nisan was also trying to get others excited for more applications of the idea, and would have loved a blog platform to do so—which he started 20 years later, in 2009.

There were of course other by-products, not only the two-prover characterization of but insights leading to PCP’s and beyond, and these came from both Chicago and a wide swath of the community.

1999: Internet Interaction

I was, however, in the loop of what Michael Nielsen regards as the first signature example of massive on-line research collaboration, the 1999 Kasparov Versus the World Internet Chess Match. It is a main running example in his new book Reinventing Discovery: the New Era of Networked Science. Well, quite possibly I caused the World to lose the game.

With sponsorship from Microsoft and First USA Bank, the match began in June 1999. The MSN Gaming Zone implementation permitted anyone (freely registered) to vote in a 24-hour period among moves recommended by four teenage masters, Étienne Bacrot of France, Florin Felecan of Romania and the US, Irina Krush of the US, and Elisabeth Pähtz of Germany. Importantly it included a bulletin board on which everyone could debate the moves and discuss anything. The move with a plurality of votes was executed, and World Champion Garry Kasparov had 24 hours to respond with his move. This alternated for what (based on previous games of this kind) was expected to be 30–40 moves and a rout by Kasparov ending in August. Instead it lasted 62 thrilling moves through October and not only drew more worldwide attention and participation than ever expected, but also impacted Kasparov’s preparation for his title defense, which was postponed and became a fateful loss to Vladimir Kramnik in 2000.

I knew about the game’s existence, but I’ve avoided online chess and was at the height of ideas for lower-bounding the permanent which we recently included here. One of my students on this project kept pumping me to look, and in late July or early August I finally did. I found that Krush was being managed by one of my childhood chess friends, Ron Henley—and to my dismay that Henley was being flamed on the MSN message boards amid general foulness. So I stepped in with a post appealing for perspective on how fascinating the endgame Krush had recommended entering was, and thereupon was hooked.

This endgame produced one of the most exciting events in chess, a multiple-pawn Queening race. I recognized that the looming position at Move 51 had even greater complexity despite having only 7 pieces, and called for organized analysis beyond any one person. It has Kasparov, playing White, to move:

Accordingly I spent a 36-hour day writing and posting a guide to the strategies. The last of my 30 bullets laid out how to organize and conduct the research. Alas my strategy bullet (11) recommended a kind of Pawn sacrifice that was followed at Move 54 but has now been proven to be the losing move, leaving us in need of traps.

We did in fact get fantastic contributions from amateur players, with pages of good analysis gathered and posted by Irina’s sponsor, SmartChess Online. The best one was a trap we were laying at Move 65 for Kasparov. However it was forestalled by a communications breakdown that prevented Irina’s crucial Move 58 recommendation from being posted at MSN, and a skin-deep alternative causing defeat four moves later was voted in. In an Orwellian turn, we had stopped talking about this trap on the BBS and kept silent on its correctness—later verified by exhaustive computer tabulation—out of paranoia that turned out to be justified: Kasparov later admitted that he was eavesdropping on the BBS. (I cut Kasparov slack on that because there should have been a stipulation from the start that masters above the 2300 level of the junior panelists could not discuss moves, while he was facing teams of grandmasters including one in St. Petersburg, Russia, long before I came on the scene.)

I am glad he thought the World’s research was valuable. There is much more I could tell even besides my articles with Irina and the book by Kasparov, but it will have to be another time.

2009: Blogs and PolyMath

Nielsen went on to aid the PolyMath Project which sprang from a 2009 blog post by Timothy Gowers.

This chapter is still being written, and we should leave it to you the readers to evaluate the effectiveness of this medium, for spurring research not just communicating it. On our part, besides this week being the two-year anniversary of the world-wide review in blog comments of Vinay Deolalikar’s still un-disposed claim to have proved , we have hosted a long–running debate on the scalability of quantum computers, and just now had some research discussion of a new way to solve linear equations.

Open Problems

How well do our brains keep up with this speed—and fanout? What might be better about research by letter?

[fixed link and my early-1990 recollection(?)]