|
Sci Tech
Bringing misconceptions to light
|
Nevanlinna Prize winner Madhu Sudan proved that considering proofs as simply `correct' or `incorrect' is a pure misconception, seeking approximation algorithms for optimisation problems is fruitless and recovering data when erroneous data is more than correct data is possible. Dr. Madhu explained the significance of his work in an e-mail interaction with R. Prasad.
|
The theory of probabilistically checkable proofs could alter our basic beliefs on how simple tasks like authentication, signing documents etc can be done efficiently over electronic media.
QUESTION: WHAT are your contributions for which you were awarded this prize?
Answer: My major contributions were in the areas of probabilistically checkable proofs, non-approximability of optimisation problems and error-correcting codes.
What in simple terms is the theory of `probabilistically checkable proof'?
Traditionally we believed that a proof of a theorem is something that checks out in every place. If there is one place where there is a logical inconsitency in the proof, then the whole proof is wrong! Furthermore, it might be possible to write proofs that have only `one inconsistency' for absurdly false theorems (most of us have seen many such proofs of "1=2"). In other words, inconsistencies in proofs are not meant to be quantified. Proofs are simply `correct' or `incorrect'. My work on probabilistically checkable proofs showed that this belief was a pure misconception. The basis of this belief was that we had fixed a `format' for the proof and then asked the question if inconsistencies could be quantified. But really `formats' are, and ought to be, modified so as to suit us.
What do you mean by `formats need to be modified to suit us'?
We need to have a format for writing proofs and a method to verify them so that a) it is not hard to come up with a correct proof for a theorem under this format as under any other format b) verification is as simple as earlier and c) inconsistencies show up almost everywhere in any purported proof of a false theorem. This in effect is the question defining the theory of probabilistically checkable proofs. Such a proof system is probabilistically checkable since we can just choose to check one of the claims in the proof at random. Since inconsistencies are abundant in proofs of false statements, we'll detect one with high probability. On the other hand if the theorem is true then there is a way to write a completely correct proof for it and then our checks will never find errors.
What is the immediate benefit of probabilistically checkable proof?
Since the proof challenges fundamental and deeply held beliefs, almost no applications were waiting in the ranks to capitalize on this resolution of the question. The one exception was the consequence to the `inapproximability of optimisation problems' (i.e.) cryptography and computer security, where the notion of a proof underlies many basic tasks that we perform. Logging in to a computer system involves `proving' your identity. Authentication, signing documents, private communication etc. are all transactions that capitalise on the ability to prove simple facts (I am X, or document Y was written by X) in clever ways and the theory of probabilistically checkable proofs could alter our basic beliefs on how to do these tasks efficiently over electronic media.
What in simple terms is non-approximability of optimisation problems?
A fundamental question in theoretical computer science is whether P equals NP. P consists of problems that are `easy' to solve with current computing methods while NP is thought to contain problems that are fundamentally harder. A fundamentally hard problem in NP has the property that a proposed solution is easily checked but that no algorithm is known that will easily produce a solution from scratch.
What is your contribution in this area?
The major impact of our result was to curb a lot of ongoing research into approximation algorithms. There were many optimisation problems for which approximation algorithms were being sought widely, and where our result showed such effort was fruitless (unless one could solve all NP-complete problems efficiently).
Let me tell you some background to explain the significance of our contribution. In 1970-72, in results that laid the foundations of modern theoretical computer science, several researchers showed that the most notorious Travelling Sale person Problem (TSP) is the hardest of its kind (NP-complete). They collected together many optimisation problems studied extensively and unsuccessfully by other mathematicians, and showed they were all NP-complete and an efficient solution to any one would imply an efficient solution to every other problem in NP (including all NP-complete ones). To the world of combinatorial optimisation this was a major negative result. Many problems, for which they would have liked to find efficient algorithms, now appeared intractable (i.e., unsolvable efficiently on a computer). Approximability of optimisation problems was introduced as a detour around the barrier of NP-completeness. The theory of NP-completeness suggested that finding the optimal tour for a travelling salesperson was intractable. A solution, where the cost of a solution is only slightly more than the cost of the optimal solution is called an approximate solution. An algorithm that finds such a solution is called an approximation algorithm. While NP-completeness suggests that finding the optimal tour is intractable, it does not rule out an efficient approximation algorithm.
What is new in your work on error-correcting codes?
Prior to our result it was widely believed that one can't recover if the amount of erroneous data is more than the amount of correct data, no matter how much redundancy you put in at the design stage. Our result shows that this was simply a misconception. You can mine a pool of data most of which is corrupted garbage and has only a small amount of correct information and extract from it some sense (provided you designed the code with sufficient redundancy to start with).
The percentage of errors that you can correct is a function of how much redundancy you put into your coding scheme and this is a design parameter. For example standard implementations of Reed-Solomon codes may put in 10 per cent redundancy into the encoding (so 90 per cent of a block of disk data is the `real data' and 10 per cent is replicated information you put in to detect and correct errors). In such a case traditional decoding would allow you to correct 5 per cent error and our new methods might allow one to correct 5.5 per cent errors. We see only a modest increase. However, the real win comes in when you put in more and more redundancy. Suppose when you designed the code you put in only 10 per cent data and 90 per cent redundancy. Standard decoding would allow you to correct only 45 per cent error while our new algorithm allows 65 per cent error. What is most significant about this number (and why this is a paradigm shift) is that now you have more errors than real data, and yet we can somehow recover from errors.
How well can you describe your work and achievement?
Perhaps two words could summarize it all: Good fortune. I ended up in theoretical computer science almost by default. When I joined IIT I elected to take up computer science without having a real sense of what it meant. At Berkeley, I drifted into theoretical computer science without realising I had done so. This trend continued as I started working first in optimisation, and then in the theory of error-correcting codes without realizing I was getting so deeply immersed.
My main results were never results I was explicitly seeking. I walked into these results (most obtained with other collaborators) while pursuing a completely different goal: an esoteric one of characterising `functions that are nearly algebraic'.
In fact, if I had known the potential consequences, I might have probably changed my research direction to try something less ambitious. On the other hand, I think my strength has been in realising the importance of a result after stumbling upon it.
How does it feel to be awarded such a coveted prize?
Certainly this is a very big honour for me. Somebody rolled a dice, and my name came up. Even the very fact that my name was considered to be worthy enough to be included on one of the sides of the dice is an honour.
Printer friendly
page
Send this article to Friends by
E-Mail
Sci Tech
|
