Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. 1st ed. 1995

種類:

電子ブック

責任表示:

edited by Madhu Sudan

出版情報:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1995

著者名:

• Sudan, Madhu.
• SpringerLink (Online service)

シリーズ名:

Lecture Notes in Computer Science ; 1001

ISBN:

9783540484851 [354048485X]    

注記:

On the resilience of polynomials -- Low-degree tests -- Transparent proofs and the class PCP -- Hardness of approximations -- Conclusions.
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.

ローカル注記:

岐阜大学構成員専用E-BOOKS (Gifu University members only)