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.

Bibliographic Information

Book Title: Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems
Editors: Madhu Sudan
Series Title: Lecture Notes in Computer Science
DOI: https://doi.org/10.1007/3-540-60615-7
Publisher: Springer Berlin, Heidelberg
eBook Packages: Springer Book Archive
Copyright Information: Springer-Verlag Berlin Heidelberg 1995
Softcover ISBN: 978-3-540-60615-4Published: 13 December 1995
eBook ISBN: 978-3-540-48485-1Published: 01 July 2005
Series ISSN: 0302-9743
Series E-ISSN: 1611-3349
Edition Number: 1
Number of Pages: XIV, 94
Topics: Algorithm Analysis and Problem Complexity, Logics and Meanings of Programs, Software Engineering, Mathematical Logic and Formal Languages, Coding and Information Theory, Numerical Analysis

Publish with us

Policies and ethics

Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems

Overview

Access this book

Other ways to access

Table of contents (6 chapters)

Front Matter

Introduction

On the resilience of polynomials

Low-degree tests

Transparent proofs and the class PCP

Hardness of approximations

Conclusions

Back Matter

Keywords

About this book

Bibliographic Information

Publish with us

Search

Navigation