In the 2012 paper On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs, the authors state the following (paraphrased from page 11).

Theorem 1 (informal). There is a PCP system where, to prove and verify that a program $P$ accepts the input $(x, w)$ within $T$ steps for some witness $w$ (with $|x|, |w| \leq T )$ [... in parallel time,] the prover runs in parallel time $O((\log T)^2)$, when also given as input the transcript of computation of $P$ on $(x, w)$ [and] the verifier runs in parallel time $O((\log T)^2)$.

I'm having trouble determining whether the authors state the asymptotic randomness used and queries made for this PCP verifier. I see that Lemma C.8 (on page 134) gives an expression for the number of queries used and amount of randomness used. However, I would be grateful if someone could interpret this into a big O notation formula.

What is the number of queries and amount of randomness used by this PCP verifier?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.