Research Catalog

Efficient checking of polynomials and proofs and the hardness of approximation problems

Title: Efficient checking of polynomials and proofs and the hardness of approximation problems / Madhu Sudan.
Author: Sudan, Madhu.
Publication: Berlin ; New York : SpringerVerlag, ©1995.

Items in the Library & Off-site

Filter by

1 Item

Item details
Status	Format	Access	Call Number	Item Location
Request for On-site Use Request Scan How do I pick up this item and when will it be ready?	Text	Use in library	QA267 .S83 1995	Off-site

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.

Subject

Genre/Form

dissertations.
Academic theses
Academic theses.
Thèses et écrits académiques.

Note

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

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
9783540606154

LCCN

95050358

OCLC

ocm33971740
33971740
SCSB-9187349

Owning Institutions

Princeton University Library