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.
- Published by
- Berlin ; New York : SpringerVerlag, ©1995.
- Author
Items in the library and off-site
Displaying 1 item
Status | Format | Access | Call number | Item location |
---|---|---|---|---|
Status | FormatText | AccessUse in library | Call numberQA267 .S83 1995 | Item locationOff-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
- NP-complete problems
- Computational complexity
- Automatic theorem proving
- Automatic theorem proving
- Computational complexity
- NP-complete problems
- Approximation
- Beweis
- Komplexität
- Komplexitätsklasse
- NP-vollständiges Problem
- Optimierungsproblem
- Polynomapproximation
- Polynomialzeitalgorithmus
- Complexité de calcul
- Théorèmes > Démonstration automatique
- Genre/Form
- dissertations.
- Academic theses
- Academic theses.
- Thèses et écrits académiques.
- 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.
- Owning institution
- Princeton University Library
- Note
- Based on the author's Ph. D. thesis, University of California, Berkeley, 1993.
- Bibliography (note)
- Includes bibliographical references (p. [73]-78) and index.