Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Reflection on the old days- by Joseph Kruskal

Expand Messages
    Guest Blog by Joe Kruskal. He is the Kruskal that did the MST algorithm, the Kruskal Tree Theorem and work on multidimensional scaling. However, this post is
    Message 1 of 1 , Nov 19, 2008
      Guest Blog by Joe Kruskal. He is the Kruskal that did the MST algorithm, the Kruskal Tree Theorem and work on multidimensional scaling. However, this post is not on any of those topics. Its a response and reflection on my post about the monotone subequence theorem.

      HIS POST:

      In your post on the monotonic sequence theorem you said the following.
      In those days it was harder to find out if someone else had done what you had done since they didn't have google, but it may have (in some cases) been easier since there were so many fewer researchers- you could just call them. OH- but long distance was expensive back then.
      Yes, long-distance phone calls were expensive then. That's why mathematicians seldom used phone calls for that purpose. They used mail -- postal mail, of course. Now that email has become almost universal, and is seen as slow and stodgy compared with text messaging and other modes of communication that I haven't kept up with, people have no real idea what communication was like 50 years before.

      The same thing was true 50 years ago. We didn't know then how communication was done 50 years before that. In England, at least, it was quite common for a well-to-do person to send a letter to a friend to propose having dinner out together, or going to a play together, or lots of other possibilities. They would expect to get a reply within say 4 hours, time enough to send another message confirming the arrangement for that evening.

      In London at least, there were 4 deliveries/pickups per day, at least for the upper classes. When my wife and I visited England in the 1950s and stayed with my sister who had moved there with her British husband, we personally observed the following, which we had been told about. When a post office mail person come to the red "post box", which displayed the pick up times, he stood there waiting until the specified pick up time, to the minute (by his watch). Only then did he open the box and take out the letters and post cards. Everyone relied on the displayed pickup times, and would hurry to the box just in time, knowing that if they got there by the posted time the mail would go out right away. Watches were not so accurate then, so I imagine that the post office pick up people checked their watches against Big Ben or other large public clocks.

      My own dissertation also indicates how things had changed:

      Paul Erdos was telling lots of people about a conjecture due to a Hungarian mathematician, Vazsonyi, he was friendly with who he said "had died", meaning that he left mathematics for a well-paying job with some company -- I think it was an airplane manufacturer. I was one of many people who heard him describe this conjecture. Roughly a year later, I had put a lot of work into this problem, but was still not close to a solution. By chance I bumped into Erdos at the Princeton Junction station. We chatted. I don't know how the conversation turned to the Vazsonyi conjecture -- probably I told him I had been working on it. He said, oh, you must read a recent paper by Rado (a British mathematician, also from Hungary). I quickly went to the library and found his paper, which I read with fear and trembling. Had I been scooped? It turned out that he had made significant progress, but hadn't cracked the nut. His work combined with mine finally led to a solution.

      Today, the equivalent of those two chance conversations can happen via Google and email. I feel certain that science of many kinds is developing much more rapidly than it used to for this reason (except, perhaps, in fields where progress is kept secret for reasons of financial gain).

      Posted By GASARCH to Computational Complexity at 11/19/2008 10:52:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.