The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
In this article we survey some of the applications that this
notion has found in the twenty years that elapsed.
These include the notion of ... more >>>

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in $NEXP$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, ... more >>>