Borrow it
Coverart for item
The Resource Efficient checking of polynomials and proofs and the hardness of approximation problems, Madhu Sudan

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

Contributor
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
Language
eng
Work
Publication
Extent
1 online resource (xiv, 87 pages).
Note
Based on the author's Ph. D. thesis, University of California, Berkeley, 1993
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
9783540484851
Instance
Label
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
Statement of responsibility
Madhu Sudan
Contributor
Subject
Language
eng
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
Member of
Cataloging source
GW5XE
Dewey number
005.1/4/015113
Index
index present
LC call number
QA267
LC item number
.S83 1995eb
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
  • theses
http://library.link/vocab/relatedWorkOrContributorName
Sudan, Madhu
Series statement
Lecture notes in computer science
Series volume
1001
http://library.link/vocab/subjectName
  • NP-complete problems
  • Computational complexity
  • Automatic theorem proving
  • Complexité de calcul (Informatique)
  • Problèmes NP-complets
  • Théorèmes
  • Automatic theorem proving
  • Computational complexity
  • NP-complete problems
  • Polynomialzeitalgorithmus
  • Komplexitätsklasse
  • Beweis
  • Optimierungsproblem
  • NP-vollständiges Problem
  • Approximation
  • Complexité de calcul
  • Théorèmes
Label
Efficient checking of polynomials and proofs and the hardness of approximation problems, Madhu Sudan
Instantiates
Publication
Copyright
Note
Based on the author's Ph. D. thesis, University of California, Berkeley, 1993
Antecedent source
unknown
Bibliography note
Includes bibliographical references (pages 73-78) and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
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
Control code
861706128
Dimensions
unknown
Extent
1 online resource (xiv, 87 pages).
File format
unknown
Form of item
online
Isbn
9783540484851
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/3-540-60615-7
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
(OCoLC)861706128
Label
Efficient checking of polynomials and proofs and the hardness of approximation problems, Madhu Sudan
Publication
Copyright
Note
Based on the author's Ph. D. thesis, University of California, Berkeley, 1993
Antecedent source
unknown
Bibliography note
Includes bibliographical references (pages 73-78) and index
Carrier category
online resource
Carrier category code
  • cr
Carrier MARC source
rdacarrier
Color
multicolored
Content category
text
Content type code
  • txt
Content type MARC source
rdacontent
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
Control code
861706128
Dimensions
unknown
Extent
1 online resource (xiv, 87 pages).
File format
unknown
Form of item
online
Isbn
9783540484851
Level of compression
unknown
Media category
computer
Media MARC source
rdamedia
Media type code
  • c
Other control number
10.1007/3-540-60615-7
Quality assurance targets
not applicable
Reformatting quality
unknown
Sound
unknown sound
Specific material designation
remote
System control number
(OCoLC)861706128

Subject

Member of

Library Locations

    • Ellis LibraryBorrow it
      1020 Lowry Street, Columbia, MO, 65201, US
      38.944491 -92.326012

Library Links

Structured data from the Bibframe namespace is licensed under the Creative Commons Attribution 4.0 International License by University of Missouri Libraries. Additional terms may apply to data associated with third party namespaces.
Processing Feedback ...