Computing from Partial Information

Authors: Anna Gal, Shai Halevi, Erez Petrank and Richard Lipton.

Reference: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999.

Abstract: We consider the question: Is finding just a part of a solution easier than finding the full solution? For example, is finding only an epsilon fraction of the bits in a satisfying assignment to a 3-CNF formula easier than computing the whole assignment? For several important problems in NP we show that obtaining only a small fraction of the solution is as hard as finding the full solution.

This can be interpreted in two ways: On the positive side, it is enough to look for an efficient algorithm that only recovers a small part of the solution, in order to completely solve any of these problems. On the negative side, any partial solution to these problems may be hard to find. Some of our results can also be interpreted as robust proofs of membership.

Keywords: NP proofs, robust proofs, fault tolerant computations, erasure correction, NP-hardness.

Availability: Paper available as Gzipped PostScript (81 Kbyte).

Shai Halevi's home page.