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 '15 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 '15 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 '15 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.