Research Catalog

Title

Efficient checking of polynomials and proofs and the hardness of approximation problems / Madhu Sudan.

Author

Sudan, Madhu.

Publication

New York : Springer, 1995.

Items in the Library & Off-site

Holdings

Details

Description

xiv, 87 pages; 24 cm.

Summary

• This work is a fascinating piece of research in computer science: it is built on and combines deep theoretical results from various areas and, at the same time, takes into account applications to hard problems in several fields.
• The author provides important new foundational insights and essentially 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.

Series Statement

Lecture notes in computer science ; 1001

Uniform Title

Lecture notes in computer science ; 1001.

Subjects

• Automatic theorem proving
• NP-complete problems
• Computational complexity

Thesis (note)

• Based on the author's Ph. D. thesis, University of California, Berkeley, 1992.

Bibliography (note)

• Includes bibliographical references (p. [73]-78) and index.

Contents

1. Introduction -- 2. On the resilience of polynomials -- 3. Low-degree tests -- 4. Transparent proofs and the class PCP -- 5. Hardness of approximations -- 6. Conclusions -- A. The Berlekamp Welch decoder -- B. Composing proof systems -- C. A characterization of NP via polynomial sequences.

ISBN

3540606157 (Berlin : softcover : alk. paper)

LCCN

95050358

OCLC

• 503586510
• ocn503586510

Owning Institutions

Columbia University Libraries