Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems
This book is based on the author's PhD thesis which was selected as the winning thesis of the 1993 ACM Doctoral Dissertation Competition. The author improved the presentation and included the progress achieved since the thesis was approved by the University of California at Berkeley. This work...
| Other Authors: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
1995, 1995
|
| Edition: | 1st ed. 1995 |
| Series: | Lecture Notes in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- On the resilience of polynomials
- Low-degree tests
- Transparent proofs and the class PCP
- Hardness of approximations
- Conclusions