From: vijay@wiliki.eng.hawaii.edu (Vijay Fafat)
Subject: Indian achievement
Organization: University of Engineering, College of Engineering
Date: Sat, 11 Apr 1992 07:15:08 GMT

Got the following article from a friend. Thought I should post it.



A group of five young researchers (the most senior member of them being 30)
made a fantastic discovery in the area of computer science. They found a way
of _transforming_ a proof (consisting of mathematical statements) to another
set of mathematical statements such that any logical mistake in the proof is
_magnified_ and is apparent at many more places. This will render the process
of proof-checking (esp. for long proofs) very easy.

What makes the news somewhat relevant in this news group is that _three_ of the
five researchers are of _Indian_ origin. Some of you may remember that
Sanjeev Arora, one of the five scientists, was the topper of JEE-1984 (?)
(Joint Entrance Examination - for admission to the five IITs in India). Some
of you may even know Madhu Sudan (from Vizag) personally.

I am reproducing a report (without the permission of its author) which some of
you may have read already.

------------------(Start)

By GINA KOLATA
c.1992 N.Y. Times News Service

       In a discovery that overturns centuries of mathematical
tradition, a group of graduate students and young researchers has
discovered a way to check even the longest and most complicated
proof by scrutinizing it in just a few spots.

[[An aside (added by PVR):

       The longest ever published proof is 15000-page long]]


       The finding, which some mathematicians say seems almost magical,
depends upon transforming the set of logical statements that
constitute a proof into a special mathematical form in which any
error is so amplified as to be easily detectable.


[[Added by PVR: This is from another article which is not included to keep the
          length reasonable (moreover, all this doesn't really belong here):

       ``Realistically, you can make the probability of missing an
error as small as 1 divided by the number of atoms in the
universe,'' Blum said. That means you can make the chance of
mistaking an incorrect proof for a correct one, ``virtually zero,''
he said.]]


       Using this new result, the researchers have already made a
landmark discovery in computer science.
       They showed that it is impossible to compute even approximate
solutions for a large group of practical problems that have long
foiled researchers.


[[Added by PVR: The following is a short note on those problems from another
           article:

       This group of thousands of problems involves finding the best
ways to do things like design telephone networks or airline routes
or to set up sequences of jobs in factories.
       Although no one has ever proved that an exact solution is
impossible, the consensus is that they are. Babai said
mathematicians had tried for centuries to find an exact solution,
to no avail.
       ``Literally thousands of people have considered these problems,
including the greatest minds in mathematics, including Gauss, and
have gotten nowhere,'' he said, referring to Karl F. Gauss, an
18th-century German mathematician and astronomer.
       In 1971, investigators showed that a wide range of these very
hard problems were mathematically equivalent: a solution to one
would solve all.]]


       Even that negative finding is very significant, experts say,
because in mathematics, a negative result, showing something is
impossible, can be just as important and open just as many new
areas of research as a positive one.
       The discovery was made by Sanjeev Arora and Madhu Sudan,
graduate students at the University of California at Berkeley, Dr.
Rajeev Motwani, an assistant professor at Stanford University, and
Dr. Carsten Lund and Dr. Mario Szegedy, young computer scientists
at AT&T Bell Laboratories.
       Motwani, who is the senior member of the group, just turned 30
on March 26.
       ``With the conventional notion of a proof, you had to check it
line by line,'' said Dr. Michael Sipser, a theoretical computer
scientist at the Massachusetts Institute of Technology. ``An error
might be buried on page 475, line 6. A `less than or equal to'
should have been a `less than.' That would totally trash the whole
proof. But you'd have to dig through the whole thing to find it,''
Sipser said.
       Now, he added, ``the new idea is that there is a way to
transform any proof so that if there is an error, it appears almost
everywhere. I'd say, `You have a proof? Show me a page.' If there
is an error, it will be there.''
       The finding, which is built on two and a one half years work by
leading researchers, is expected to have a profound impact. But
because it is so new and unexpected, mathematicians and computer
scientists cannot yet predict its scope of application.
       ``This is philosophically important,'' said Dr. Mihalis
Yannakakis, a theoretical computer scientist at AT&T Bell
Laboratories.
       Dr. Manuel Blum, a mathematician at the University of California
at Berkeley, agreed that the result was ``really exciting,'' with
ramifications that were hard to predict.
       The new verification method can show up errors in calculations
as well as in proofs, experts said, and Blum suggested it could
have a role in checking long computer computations.
       Dr. Umesh Vazirani, a theoretical computer scientist at the
University of California at Berkeley, said that the discovery was
``one of the most outstanding in the past decade,'' because it
allowed investigators to decide, almost at a glance, whether it was
worthwhile to try to find an approximate solution to a problem they
were unable to solve exactly.
       ``As soon as you formulate a problem, you can know if it is
intractable,'' Vazirani said.
       The finding is so recent that it has not yet been published.
``We just wrote it in the last month or so,'' Motwani said.

------------------(End)