Return to Answer

Note: We're actually traversing a tree that has polynomial depth, and exponential fan-out. The base case corresponds to the leaves of the tree. So we have the max-nodes and average-nodes, and to compute the root's value, we kinda apply a standard tree traversal algorithm, which which takes at most polynomial space.

Note: We're actually traversing a tree that has polynomial depth, and exponential fan-out. The base case corresponds to the leaves of the tree. So we have the max-nodes and average-nodes, and to compute the root's value, we kinda apply a standard tree traversal algorithm, which takes at most polynomial space.

Credit to: I recall the idea from a lecture of Alessandro Chiesa that I saw online two years ago, but unfortunately I do not recall where or whether it is still up there.

Note: We're actually traversing a tree that has polynomial depth, and exponential fan-out. The base case corresponds to the leaves of the tree. So we have the max-nodes and average-nodes, and to compute the root's value, we kinda apply a standard tree traversal algorithm, which which takes at most polynomial space.

Credit to: I recall the idea from a lecture of Alessandro Chiesa that I saw online two years ago, but unfortunately I do not recall where or whether it is still up there.

where $a^*_j$ is the best prover message obtained by simulating an interaction that is consistent with $x, r$ and $(a_1, b_1, \ldots, a_i, b_i)$. So once $a_{i+1}$ and $r$ are fixed and we are in the inner loop, we can compute $b_{i+1} = V(x, r, a_1, a_2, \ldots, a_{i+1})$, $a^*_{i+2} = P_b(x, r, a_1, b_1, \ldots,a_{i+1}, b_{i+1} )$ and proceed similarly to compute $b_{i+2}$ and $a^*_{i+3}$, etc. The point is that inside the inner loop, we can compute $a^*_j$ in polynomial space as we are applying the induction hypothesis and computing $P_b$ on transcripts with $ > i$ rounds. So we kinda open an inner third loop to do that, but it takes at most polynomial space in total as the induction assumption takes care of that.

where $a^*_j$ is the best prover message obtained by simulating an interaction that is consistent with $x, r, a_{i+1}$ and $(a_1, b_1, \ldots, a_i, b_i)$. So once $a_{i+1}$ and $r$ are fixed and we are in the inner loop, we can compute $b_{i+1} = V(x, r, a_1, a_2, \ldots, a_{i+1})$, $a^*_{i+2} = P_b(x, r, a_1, b_1, \ldots,a_{i+1}, b_{i+1} )$ and proceed similarly to compute $b_{i+2}$ and $a^*_{i+3}$, etc. The point is that inside the inner loop, we can compute $a^*_j$ in polynomial space as we are applying the induction hypothesis and computing $P_b$ on transcripts with $ > i$ rounds. So we kinda open an inner third loop to do that, but it takes at most polynomial space in total as the induction assumption takes care of that.