3

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 ?

Community
  • 1
Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • 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. – hirsch May 06 '15 at 10:37
  • You mean http://eccc.hpi-web.de/report/2012/077/ ? I don't see any comments after Theorem 1. – Suresh Venkat May 06 '15 at 16:05
  • I mean "Comment #2" to this report (this is a different file with a different set of authors). A direct link:http://eccc.hpi-web.de/report/2012/077/comment/2/download/ – hirsch May 07 '15 at 16:18

0 Answers0