mirror-textfiles.com/bbs/KEELYNET/UNCLASS/probnet.asc

                (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