Efficient checking of polynomials and proofs and the hardness of approximation problems /
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis Book |
| Language: | English |
| Published: |
Berlin ; New York :
Springer?b-?sVerlag,
c1995.
|
| Series: | Lecture notes in computer science ;
1001. |
| Subjects: |
| LEADER | 02155nam a2200337 a 4500 | ||
|---|---|---|---|
| 001 | c000175367 | ||
| 003 | CARM | ||
| 005 | 19960514000000.0 | ||
| 008 | 951211s1995 gw b 001 0 eng | ||
| 010 | |a 95050358 | ||
| 019 | 1 | |a 12096237 |5 LACONCORD2021 | |
| 020 | |a 3540606157 | ||
| 035 | |a (OCoLC)33971740 |5 LACONCORD2021 | ||
| 040 | |a TOC |b eng |c TOC |d TOC | ||
| 050 | 0 | 0 | |a QA267 |b .S83 1995 |
| 082 | 0 | 0 | |a 005.1/4/015113 |2 20 |
| 100 | 1 | |a Sudan, Madhu. | |
| 245 | 1 | 0 | |a Efficient checking of polynomials and proofs and the hardness of approximation problems / |c Madhu Sudan. |
| 260 | |a Berlin ; |a New York : |b Springer?b-?sVerlag, |c c1995. | ||
| 300 | |a xiv, 87 p. ; |c 24 cm. | ||
| 440 | 0 | |a Lecture notes in computer science ; |v 1001. | |
| 502 | |a Based on the author's Ph. D. thesis, University of California, Berkeley, 1993. | ||
| 504 | |a Includes bibliographical references (p. [73]-78) and index. | ||
| 505 | 0 | |a 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. | |
| 520 | |a 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. | ||
| 650 | 0 | |a NP-complete problems. | |
| 650 | 0 | |a Computational complexity. | |
| 650 | 0 | |a Automatic theorem proving. | |
| 852 | 8 | |b CARM |h A2:AP19D0 |i C07236 |p 0239298 |f BK | |
| 999 | f | f | |i 1c3abaaf-698f-540d-a01c-1b4ab6b865ce |s d9124264-f6da-55b6-808b-dddad56f0a3e |
| 952 | f | f | |p Can circulate |a CAVAL |b CAVAL |c CAVAL |d CARM 1 Store |e C07236 |f A2:AP19D0 |h Other scheme |i book |m 0239298 |