Interactive and probabilistic proof-checking

✍ Scribed by Luca Trevisan

• Book ID: 104307049
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 112 KB
• Volume: 104
• Category: Article
• ISSN: 0168-0072
• DOI: 10.1016/s0168-0072(00)00017-8

✦ Synopsis

The notion of e cient proof-checking has always been central to complexity theory, and it gave rise to the deÿnition of the class NP. In the last 15 years there has been a number of exciting, unexpected and deep developments in complexity theory that exploited the notion of randomized and interactive proof-checking. Results developed along this line of research have diverse and powerful applications in complexity theory, cryptography, and the theory of approximation algorithms for combinatorial optimization problems. In this paper we survey the main lines of developments in interactive and probabilistic proof-checking, with an emphasis on open questions.