Efficient checking of polynomials and proofs and the hardness of approximation problems /
This work is a fascinating piece of research in computer science: it is built on and combines deep theoretical results from various areas and, at the same time, takes into account applications to hard problems in several fields. The author provides important new foundational insights and essentially...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis Book |
| Language: | English |
| Published: |
Berlin ; New York :
Springer?b-?sVerlag,
c1995.
|
| Series: | Lecture notes in computer science ;
1001. |
| Subjects: |
Table of Contents:
- 1. Introduction
- 2. On the resilience of polynomials
- 3. Low-degree tests
- 4. Transparent proofs and the class PCP
- 5. Hardness of approximations
- 6. Conclusions
- A. The Berlekamp Welch decoder
- B. Composing proof systems
- C. A characterization of NP via polynomial sequences.