The basic treatment of interactive proof systems ignores the complexity of proving, but it is clear that the latter is an important notion (especially if one thinks of applying an interactive proof system rather than use it towards some theoretical study). The complexity of proving membership in a set $S$ can be related to either (1) the non-deterministic complexity of the set $S$, (2) the complexity of a randomized reduction to $S$, or (3) the deterministic complexity of the set $S$. These relations give rise to three different notions of relative efficiency (of the proving task) reviewed in Section 9.1.5.1 of my computational complexity book. The 1st notion is useful when relating different proof systems and it is justifiable in application in which the prover has a proof relative to one system (typically an NP-proof) and wishes to produce a proof wrt a different proof system (e.g., a zero-knowledge one). The 2nd notion yields a natural generalization of the notion of self-reducibility (of NP-sets). The 3rd notion is the one discussed in the current paper (following Goldwasser-Kalai-Rothblum). In particular, the focus is on efficient (i.e., polynomial-time) proving strategies that allow super-fast verification. Indeed, we consider proving membership in P-sets, the (designated) prover strategies will run in polynomial-time, but the point is that verification will be much easier that deciding membership in the set.
In GKR super-fast verification meant almost-linear time (and one of their results was that any set in NC has such a proof system). In the current work, super-fast means sublinear-time, which means that the verifier cannot even read the input. Thus, standard proof systems (which correspond to exact decisions) may not exist (except for degenerate sets) and we can only expect approximate decisions in the spirit of property testing. Indeed, the new notion of interactive proofs of proximity correspond to standard interactive proofs analogously to the way that property testers correspond to standard decision procedures (and analogously to the way that PCPs of proximity correspond to standard PCPs). N.B.: interactive proofs of proximity are meaningful even if the prover strategy is not efficient, but in the current work the focus is on interactive proofs of proximity that do have efficient prover strategies. One of their results is that any set in NC has such an interactive proof of proximity (i.e., sublinear-time verification and polynomial-time prover strategies).
We initiate the study of interactive proofs with sublinear time verifiers. These proof systems can be used by a sublinear-time client for delegating computation: the client, who only has (reliable) query access to a potentially huge input, can interact with a powerful but unreliable server who has full access to the input. The client can delegate its computations to the server, and receive a proof of approximate correctness for the results.
As in the study of sublinear time algorithms, randomness is essential. Following the literature on property testing, we seek proof systems where with high probability the verifier accepts every input in the language, and rejects every input that is far from the language. The verifier's query complexity (and computation complexity), as well as the communication, should all be sublinear. We call such a proof system an Interactive Proof of Proximity. We explore the power of this model and show general upper and lower bounds.