Fast approximate PCPs
Funda Ergün, Ravi Kumar, Ronitt Rubinfeld · 1999
We investigate the problem of when a prover can aid a verifier to reliably compute a functionfaster than if the verifier were to compute the function on its own.We focus on the case when it is enough for the verifier to know that the answer is close to correct.We use a model of proof systems which is based on interactive proof systems, probabilistically checkable proof systems, program checkers, and CS proofs.We develop protocols for several optimization problems, in which the running time of the verifier is significantly less than the size of the input.For example, we give polylogarithmic time protocols for showing the existence of a large Cut, a large matching and a small bin packing.In contrast, the protocolsused to show that IP = PSPACE, MIP = NEXP and NP = PCP(lg n, 1) [Sha90, BFL91, ALM+98, BFLS90J require a verifier that runs in sl(n) time.In the process, we develop a set of tools for use in constructing these proof systems.