On the Efficiency of Non-Uniform PCPP Verifiers.
Or Meir · 2008
We define a non-uniform model of PCPs of Proximity, and observe that in this model the non-uniform verifiers can always be made very efficient. Specifically, we show that any nonuniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity.