Efficient checking of polynomials and proofs and the hardness of approximation problems
Author(s)
Bibliographic Information
Efficient checking of polynomials and proofs and the hardness of approximation problems
（Lecture notes in computer science, 1001）
Springer-Verlag, c1995
Available at / 54 libraries
-
Library, Research Institute for Mathematical Sciences, Kyoto University数研
L/N||LNCS||100195067618
-
University of Tsukuba Library, Library on Library and Information Science
007.08:L-49:1001951014090
-
No Libraries matched.
- Remove all filters.
Note
Bibliography: p. [73]-78
Includes index
Description and Table of Contents
Description
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 is a fascinating piece of theoretical computer science research building on deep results from different areas. It provides new theoretical insights and advances applicable techniques in such different areas as computational complexity, efficient (randomized) checking of proofs, programs and polynomials, approximation algorithms, NP-complete optimization, and error-detection and error-correction algorithms in coding theory.
Table of Contents
On the resilience of polynomials.- Low-degree tests.- Transparent proofs and the class PCP.- Hardness of approximations.- Conclusions.
by "Nielsen BookData"
