Efficient checking of polynomials and proofs and the hardness of approximation problems
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.
- Highly resilient correctors for polynomials
- Non-interactive proofs of proximity
- Algebraic testing and weight distributions of codes.
- Self-correcting polynomial programs
- Approximate CVP in time \(2^{0.802 n}\) -- now in any norm!
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- Public key locally decodable codes with short keys
- Short locally testable codes and proofs
- The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear
- A novel elementary construction of matching vectors
- A hierarchy theorem for interactive proofs of proximity
- Constant-round interactive proofs for delegating computation
- Relaxed locally correctable codes
- Constant-round arguments from one-way functions
- On quasilinear-time complexity theory
- Polynomial-time pseudodeterministic construction of primes
This page was built for publication: Efficient checking of polynomials and proofs and the hardness of approximation problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1906841)
