(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