Overview

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.

Full Product Details

Author:   Madhu Sudan
Publisher:   Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
Imprint:   Springer-Verlag Berlin and Heidelberg GmbH & Co. K
Edition:   1995 ed.
Volume:   1001
Dimensions:   Width: 15.50cm , Height: 0.50cm , Length: 23.50cm
Weight:   0.454kg
ISBN:  

9783540606154

ISBN 10:   3540606157
Pages:   94
Publication Date:   13 December 1995
Audience:   College/higher education ,  Professional and scholarly ,  Postgraduate, Research & Scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

Table of Contents

On the resilience of polynomials.- Low-degree tests.- Transparent proofs and the class PCP.- Hardness of approximations.- Conclusions.

Reviews

Author Information

Tab Content 6

Author Website:  

Countries Available

All regions