Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems

1995
ISBN: 978-3-540-60615-4
Verlag: Springer Berlin Heidelberg

Buch, Englisch, Band 1001, 94 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 178 g

Reihe: Lecture Notes in Computer Science

This book is based on the author's PhD thesis which was selected as the winning thesis of the 1993 ACM Doctoral Dissertation Competition. The author improved the presentation and included the progress achieved since the thesis was approved by the University of California at Berkeley.
This work is a fascinating piece of theoretical computer science research building on deep results from different areas. It provides new theoretical insights and 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.

Zielgruppe

Research

Autoren/Hrsg.

Sudan, Madhu

Fachgebiete

• Mathematik | Informatik EDV | Informatik Daten / Datenbanken Informationstheorie, Kodierungstheorie
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Programmierung: Methoden und Allgemeines
• Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten
• Mathematik | Informatik Mathematik Mathematische Analysis
• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Software Engineering Objektorientierte Softwareentwicklung
• Interdisziplinäres Wissenschaften Wissenschaften: Forschung und Information Informationstheorie, Kodierungstheorie
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Numerische Mathematik

Inhaltsverzeichnis

On the resilience of polynomials.- Low-degree tests.- Transparent proofs and the class PCP.- Hardness of approximations.- Conclusions.