About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Information and Computation
Paper
Fast approximate probabilistically checkable proofs
Abstract
We investigate the question of when a verifier, with the aid of a proof, can reliably compute a function faster than it can without the proof. The proof system model that we use is based on a variant of the Probabilistically Checkable Proofs (PCP) model, in which a verifier can ascertain the correctness of the proof by looking at very few locations in the proof. However, known results in the PCP model require that the verifier spend time linear in the size of the input in order to determine where to query the proof. In this work, we focus on the case when it is enough for the verifier to know that the answer is close to correct, and develop an approximate PCP model. We construct approximate PCPs for several optimization problems, in which the total running time of the verifier is significantly less than the size of the input. For example, we give polylogarithmic time approximate PCPs for showing the existence of a large cut, or a large matching in a graph, and a small bin packing. In the process, we develop a set of tools for use in constructing these proof systems. © 2003 Elsevier Inc. All rights reserved.