In an interactive proof, there are a number of resources that can be traded off against each other. For example, verifier time, verifier space (as per this question), amount of randomness used, number of bits of proof probed (for PCPs), the number of rounds, and so on.

Is there any survey of the known tradeoffs between the different resources used in an interactive proof ?

  • $\begingroup$ I don't know about a survey. For IP, the space (deterministic space) is related to the communication and verifier's space, see Comment #2 to ECCC TR12-077, Theorem 1. $\endgroup$
    – hirsch
    May 6, 2015 at 10:37
  • $\begingroup$ You mean eccc.hpi-web.de/report/2012/077 ? I don't see any comments after Theorem 1. $\endgroup$ May 6, 2015 at 16:05
  • $\begingroup$ I mean "Comment #2" to this report (this is a different file with a different set of authors). A direct link:eccc.hpi-web.de/report/2012/077/comment/2/download $\endgroup$
    – hirsch
    May 7, 2015 at 16:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.