Explicit communication, round, and evaluation bounds

The protocol has one prover message in each reached round of its $T$-round schedule and no other prover message, because the initial claim $1$ is the verifier's own constant and the terminal step uses the verifier's evaluation of $b$; the operator list has $T=n(n+3)\mathrm{/}2=n^2\mathrm{/}2+3n\mathrm{/}2$ entries by [A2], so at most $T=O(n^2)$ prover messages are sent, with equality if all checks pass, and claim 1 holds. This includes $n=0$, where $T=0$ and there is no message at all.

Each message is a list of $D+1$ coefficients by [A1], and a coefficient is a residue represented by an integer in $\{0,\dots ,p-1\}$; by [A3] each such integer needs $\lceil {\log }_{2}p\rceil =O(\log (TD+2))$ bits, so a message costs $(D+1)\lceil {\log }_{2}p\rceil$ bits and the prover communication is at most $T(D+1)\lceil {\log }_{2}p\rceil$ bits. At most $T$ residue challenges add at most $T\lceil {\log }_{2}p\rceil$ bits, giving the stated two-way bound. Since $n$ and $L$ are bounded by the input length and $D=\max \{L,2\}$, this is polynomial in the input length, which is claim 2.

Each round whose check passes reads exactly one block of $k=2\lceil {\log }_{2}p\rceil$ bits, so the run reads at most $2T\lceil {\log }_{2}p\rceil$ random bits in total. In a round with a legal message the verifier evaluates it at the two Boolean points and, if the check passes, at the challenge, which is at most three Horner evaluations of a degree-$D$ polynomial: by [A3] this costs $O(D)$ field operations, or $O(D{\log }^{2}p)$ bit operations, per round. This is claim 3.

If the terminal step is reached, the verifier evaluates $b$ at one point of $F^n$ using the arithmetic circuit of $\psi$; by [L1] this costs $O(L)$ field operations, hence $O(L{\log }^{2}p)$ bit operations by [A3]. The rounds contribute $O(TD{\log }^{2}p)$ bit operations by step 1.3, including the constant-size identity checks, fixed-width message checks and reduction of each challenge block modulo $p$. Thus the rounds and terminal step together cost $O((TD+L){\log }^{2}p)$ bit operations.

For $T\ge 1$, the prime-search clause of A polynomial-size prime field meets the soundness budget supplies the additional $O(N^2{\log }^{2}N)$ bit-operation cost: there are at most $N^2$ trial divisions, each on $O(\log N)$-bit integers. For $T=0$, [A1] sets $p=3$ in constant time, also within that bound. Adding this setup cost to step 2.1 gives claim 4. Since $N=\max \{2,12TD+1\}$ and $n,L$ are bounded by the input length, the total bound is polynomial. All bounds hold for every random tape and every prover, with malformed messages rejected at the fixed message-length cap, so they are worst-case bounds.