Do you phrasing the definition of the events $G_i$ from question 1 of hw5 a bit more formally, or just differently? I'm having trouble parsing it.

I don't understand what it means for $G_i$ to occur.

Added details, and posted a revised version.

I feel additional clarification is needed.

For p_i to have a value, the (i-1) interactions should be fixed as you stated. Does that mean that whenever the question is refering to G_i and probabiliy of it (such as in section a) we can assume t interactions were fixed and they're not random event ? otherwise, what meaning could p_i > 1 - 1/|E| have ?

Another question, perhaps semantic, V is said to accept in the i-th interaction. It makes more sense to me if it would say that V accepts (all interactions) up until the i-th interaction, because V is obviously aware to all prior interactions.

Thanks.

$p_i$ is well defined for any fixing of the first $i-1$ interactions. When you sample $t$ interactions according to the described random process, you can talk about the probability that the first $i-1$ interactions are such that $p_i$ is high.

We care about the probability that $V$ accepts in a given interaction after the previous interactions have been fixed. Redefining $G_i$ is not necessary (although it is possible, since we're anyhow looking at the intersection with the event that $V$ accepts in all interactions).

Another question re Q1:

Until now we only encountered "oracle access" to non-interactive entities. So what does it mean to have "oracle access" to an interactive prover? Does it mean we can run the interactive protocol against it many times (each time starting from the beginning)? Or can we also emulate its running?

Good question, we discussed this in class, but weren't formal about it.

This means that we can "rewind" $P^*$ —- any partial interaction in the first $i-1$ rounds, can be continued many times where the extractor can choose different verifier messages the $i+1$st message.

Few more questions. Denote the next message function of $P^*$ as $f$.

1. In the GMW zk-proof for 3col, the interaction between prover and verifier was consists of commitments, edge, coloring. So saying that $f$ receive the transcript so far, meaning it receives set of edges asked so far? i.e. $e_1, ..., e_k$

2. Why when we fixing the $i-1$ interactions, $p_i$ became fixed? Isn't all $p_i$ independents? Because $V$ chooses random edge for every interaction, all the interactions between the prover and verifier are independent too. What I'm missing?

3. I assume the extractor should succeed w/ probability 1. However theoretically speaking, the prover manages to convince us w/ some success rate. Isn't it make it impossible to "always extract" coloring? Cause maybe he's assignment isn't valid for some edge.

1. Since we're thinking of a deterministic prover, the verifier's queries (i.e. the edges it asks to open) indeed fix the entire transcript as you say.

2. Once you fix some first $i-1$ interactions, you can now ask what's the probability (over the verifier's next query) that the prover will answer correctly, this probability is what we call $p_i$.

3. The extractor can extract with probability one in expected poly-time, or with probability $1-n^{-\omega(1)}$ in fixed poly-time. This indeed shows that a prover that always answers according to an assignment that is invalid on some edge will fail to convince us in some iteration, except with negligible probability.

I don't understand why the extractor is probabilistic. Since we only need to prove the existence of the extractor, isn't it enough to say that $G_i$ is nonzero with some probability, so there is some fixed set of interactions and random coins of $V$ that cause $p_i$ to be larger than $1-\frac{1}{|E|}$? The extractor can just query the oracle using that transcript. Or does the extractor have to be uniform?