Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems
Madhu Sudan · 1996
The definition of the class NP [Coo71, Lev73] highlights the problem of verification of proofs as one of central interest to theoretical computer science. Recent efforts have shown that the efficiency of the verification can be greatly improved by allowing the verifier access to random bits and accepting probabilistic guarantees from the verifier [BFL91, BFLS91, FGL + 91, AS92]. We improve upon the efficiency of the proof systems developed above and obtain proofs which can be verified probabilistically by examining only a constant number of (randomly chosen) bits of the proof. The efficiently verifiable proofs constructed here rely on the structural properties of low-degree polynomials. We explore the properties of these functions by examining some simple and basic questions about them. We consider questions of the form: • (testing) Given an oracle for a function f, is f close to a low-degree polynomial? • (correcting) Let f be close to a low-degree polynomial g, is it possible to efficiently reconstruct the value of g on any given input using an oracle for f? 2 The questions described above have been raised before in the context of coding theory as the problems of error-detecting and error-correcting of codes. More recently