<p>In an interactive proof, there are a number of resources that can be traded off against each other. For example, verifier time, verifier space (<a href="https://cstheory.stackexchange.com/a/12385/80">as per this question</a>), amount of randomness used, number of bits of proof probed (for PCPs), the number of rounds, and so on. </p>

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

CC BY-SA 3.0
2015-05-06T10:37:23.140Z
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
CC BY-SA 3.0
2015-05-06T16:05:53.513Z
You mean http://eccc.hpi-web.de/report/2012/077/ ? I don't see any comments after Theorem 1.
Suresh Venkat
CC BY-SA 3.0
2015-05-07T16:18:08.670Z
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
<cc.complexity-theory><interactive-proofs>
Resource tradeoffs in interactive proofs
Suresh Venkat
# Resource tradeoffs in interactive proofs

(Asked by: username_0 on 2015-05-06)

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](https://cstheory.stackexchange.com/a/12385/80)), 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 ?

**Tags:** cc.complexity-theory, interactive-proofs
> **Comments:**
> **username_1**: 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.  
> **username_0**: You mean http://eccc.hpi-web.de/report/2012/077/ ? I don't see any comments after Theorem 1.  
> **username_1**: 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/  

---

## 0 answers

