Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.