03935nam 22007695 450 99646603950331620200703051625.03-540-48485-X10.1007/3-540-60615-7(CKB)1000000000016922(SSID)ssj0000322819(PQKBManifestationID)11247853(PQKBTitleCode)TC0000322819(PQKBWorkID)10288092(PQKB)11587295(DE-He213)978-3-540-48485-1(PPN)155206877(EXLCZ)99100000000001692220121227d1995 u| 0engurnn|008mamaatxtccrEfficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems[electronic resource] /edited by Madhu Sudan1st ed. 1995.Berlin, Heidelberg :Springer Berlin Heidelberg :Imprint: Springer,1995.1 online resource (XIV, 94 p.) Lecture Notes in Computer Science,0302-9743 ;1001Bibliographic Level Mode of Issuance: Monograph3-540-60615-7 On the resilience of polynomials -- Low-degree tests -- Transparent proofs and the class PCP -- Hardness of approximations -- Conclusions.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.Lecture Notes in Computer Science,0302-9743 ;1001AlgorithmsComputer logicSoftware engineeringMathematical logicCoding theoryInformation theoryNumerical analysisAlgorithm Analysis and Problem Complexityhttps://scigraph.springernature.com/ontologies/product-market-codes/I16021Logics and Meanings of Programshttps://scigraph.springernature.com/ontologies/product-market-codes/I1603XSoftware Engineeringhttps://scigraph.springernature.com/ontologies/product-market-codes/I14029Mathematical Logic and Formal Languageshttps://scigraph.springernature.com/ontologies/product-market-codes/I16048Coding and Information Theoryhttps://scigraph.springernature.com/ontologies/product-market-codes/I15041Numerical Analysishttps://scigraph.springernature.com/ontologies/product-market-codes/M14050Algorithms.Computer logic.Software engineering.Mathematical logic.Coding theory.Information theory.Numerical analysis.Algorithm Analysis and Problem Complexity.Logics and Meanings of Programs.Software Engineering.Mathematical Logic and Formal Languages.Coding and Information Theory.Numerical Analysis.005.1/4/015113Sudan Madhu753660Sudan Madhuedthttp://id.loc.gov/vocabulary/relators/edtBOOK996466039503316Efficient checking of polynomials and proofs and the hardness of approximation problems1516200UNISA