(word processor parameters LM=8, RM=78, TM=2, BM=2) Taken from KeelyNet BBS (214) 324-3501 Sponsored by Vangard Sciences PO BOX 1031 Mesquite, TX 75150 August 17, 1990 courtesy of Double Helix BBS at 212-865-7043 -------------------------------------------------------------------- Mathematical Feeding Frenzy: How a network was used to solve a problem From the Tuesday June 26,1990 New York Times: By Gina Kolata. In what could be described as a feeding frenzy, a mathematical advance went from promising concept to completed result in a matter of weeks through an informal worldwide competition conducted by electronic mail. While the result was exciting, researchers say its true importance lay in the way it was reached. "I have never seen anything like this," said Dr. Ronald Rivest,` mathematician and computer scientist at the Massachusetts Institute of Technology who watched from the sidelines as the research rush went on. "Computer networks are replacing professional journals and conferences." ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ The new electronic mail competition will be likely in many other fields as well because physicists and biochemists, for example, are also increasingly hooked up to computer networks, said Dr. Fan Chung, a research mathematician who is division manager of mathematics, operations research and information science at Bell Communications Research in Morristown, New Jersey. Investigators say they have mixed feelings about the predicted onslaught of rapid-fire results from computer network competitions. Many suggest the networks will increase collaboration on difficult problems, generate excitement and result in faster solution of problems. But Dr. Laszlo Babai of the University of Chicago, who participated in the recent competition, said that proofs by electronic mail place some researchers at a disadvantage. He said scientists in Eastern Europe, third world countries and even much of Japan are not hooked up electronically the way these in the United States, Western Europe and Israel are. In addition, Dr. Babai added, researchers who help the work on its way but do not get the final answer can feel deprived of the Page 1 credit they would have got if the work had proceeded at a more measured pace. "All the credit goes to the one who did the last step", Dr. Babai said. ------------------------------------------------------------- Note (from Jeff Jennings of Double Helix) : I'm wondering here how much of this was computers and how much was the fact of a competition. There was no actual competition here except the desire to solve the problem first. I'd say however the computers made the competition possible which otherwise could only be done by people in close proximity to each other in the same organization. The quickest way to advance things for the least cost has always been a prize. It would be better to have government prizes rather than government grants except that historically, going back to the 17OO's and the invention of a clock that was good at sea, governments have not been too good in keeping their promises of rewards. The other problem is getting started, some money has to be advanced up front. The article now continues and tells the story: ------------------------------------------------------------- The race began on Nov. 27 when Dr. Noam Nisan, a postdoctoral student at the Massachusetts Institute of Technology, got an idea that could overturn mathematicians' ideas of how difficult certain problems are. [It is kind of an estimate of how hard it would be to solve certain problems] Researchers have been stymied by a series of practical problems that sound simple but that seem to be so difficult to solve that they are almost beyond comprehension. Their solutions require so many computations that they make seemingly large numbers, like the number of atoms in the universe [according to some calculation, of course], look trivial. So mathematicians and computer scientists have looked for ways to determine whether a problem is going to be impossible to solve. When asked for an example of a difficult problem, mathematicians invariably trot out the one they call the Traveling Salesman. A salesman has to find a route that takes him through a group of cities. What is the shortest possible distance he must travel to visit each city once? It sounds easy and it is important. The routing of telephone lines, for example, is a traveling salesman problem. But it turns out that the only way anyone knows to get a general answer to such a problem is to try every route. [Sounds like stuff for a game] Checking a Million Billion Routes Dr. Chung has calculated that if a computer can check a million billion routes every second, and if the computer started cranking Page 2 away at the beginning of the universe, it would have taken until 1990 to check all the possible routes for a tour of 33 cities. [I suppose January 6,1990 to be precise] When problems get to be that hard, mathematicians have had trouble categorizing them in classes according to how difficult they really would be to solve. They had devised a classification scheme, but the scheme was difficult to verify. But Dr. Nisan, inspired by recent related discoveries by Dr. Richard Liptin of Princeton University, Dr. Joan Feigenbaum of AT&T Bell Laboratories, and a Harvard graduate student, Donald Beaver, suggested that it might be possible to use a probabilistic proving system, where a fact can almost be verified -- but not to absolute certainty -- to collapse some of the previous classifications. "This went against all previous intuition, " Dr. Babi said, and it caused enormous excitement among researchers. If Dr. Nisan's idea was correct, it could mean that some of these problems were not as hard as they had been thought to be. Dr. Nisan says he sent his idea out to about 10 friends by computer mail, and then went home to Jerusalem, where he had accepted a position on the faculty of Hebrew University. Almost immediately afterward, he left for Brazil on vacation. While Dr. Nisan was away, mathematicians around the world distributed his idea to each other and began working on it at a frenzied pace. Seventeen days later, Dr. Carsten Lund, Dr. Lance Fortnow and Dr. Howard Karloff of the University of Chicago sent out the next leap forward on electronic mail and their result was copied and recopied by computers around the world. Thirteen days later, Dr. Adi Shamir, a mathematician at the Weizmann Institute of Science at Rehovot, Israel, hit the jackpot, announcing, once again, through electronic mail, that Dr. Nisan's original idea was correct and that he could prove it. Finally, 22 days later, the University of Chicago group, including Dr. Babai, put the final touches on the result. Last Wednesday [ = June 20,1990.] again by electronic mail, the competing groups got notice that five papers on the result had been accepted for a highly selective scientific meeting to be held next October. Dr. Chung said, "If Noam Nisan did not put his stuff on the network, if he had just worked on it by himself, it is the opinion of everyone that he should have been able to figure out the whole thing." But Dr. Nisan said that he was not concerned that he had been left out of the race. "I've heard some people say I should have kept the idea a secret," he said. "But it's supposed to be a great compliment when people work on your ideas. I thought it was very nice and I don't think bad things will happen to my career." Page 3