Efficient checking of polynomials and proofs and the hardness of approximation problems (Q1906841)

The book represents the author's Ph.D. distinguished thesis at Berkeley (California, 1992). This dissertation describes general techniques to approach the NP-completeness problems of establishing the computational tractability of approximation problems. Approximation hardness is established for all NP-complete problems (with P\(\neq\)NP) in the complexity class max-SNP: this includes basic problems such as the Euclidean traveling salesman problem, max-2SAT, Euclidean Steiner tree, or other problems related to chromatic number, set cover, and shortest vector in a lattice. The M. Sudan's book provides a new characterization of the complexity class NP, showig that any NP language admits an efficient probabilistically checkable proof of membership. The membership robust proofs are still polynomially long, and can be checked by probing only a constant number of randomly chosen bits of the proof. Other remarkable achievements within the book are: (a) a beautiful technique for creating long but very robust proofs based on self-correction properties of linear functions; (b) a new low-degree test that probes the value of a multivariate function at only a constant number of points and verifies whether it is close to some low-degree polynomial; (c) in the context of coding theory, fast and randomized algorithms for error-detection and error-correction of (some well-known) codes. In sum, a book containing consistent, technical, and deep results for theoretical computer science.