ENGLISH

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

By Madhu Sudan (eds.)

Book information

Publisher
Springer-Verlag Berlin Heidelberg
Year
1995
ISBN
3540606157, 9783540606154
DOI
10.1007/3-540-60615-7
LCC
QA267 .S83 1995
Open Library ID
OL813100M
Language
english
Format
DJVU
Filesize
736 kB (753746 bytes)
Series
Lecture Notes in Computer Science 1001
Edition
1
Pages
94\98
Topic
Computers
Library
Kolxo3
DPI
300
Scanned
yes
Time added
2009-07-20 03:45:11
Algorithm Analysis and Problem Complexity; Logics

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.

Similar books