Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-064 | 11th July 2008 00:00

On the Efficiency of Non-Uniform PCPP Verifiers

RSS-Feed




TR08-064
Authors: Or Meir
Publication: 11th July 2008 14:58
Downloads: 2951
Keywords: 


Abstract:

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 non-uniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity.



ISSN 1433-8092 | Imprint