A seemingly side issue that has puzzled me for a while is how to state results of the current type. Specifically, we seek a universal procedure (in this case the prover strategy) that runs in time that is linear in the complexity of the problem, where the universal procedure is doing something other than deciding the problem. The point is that the standard emulations of a computation do involve a super-constant overhead. Furthermore, if one uses circuits as their computational model, then there is a logarithmic factor difference between the size of the circuit (i.e., our measure of complexity) and the description of the circuit (to be given as input to a universal procedure).
The suggested solution, for the context of the circuit model, is to use a non-universal procedure (say for proving) and allow it to depend arbitrarily on the circuit that defines the problem (i.e., the deciding circuit) and relate the complexity of the two circuits (i.e., their sizes). Of course, on top of this, one may require an efficient transformation of the first circuit to the second circuit, but this (universal) complier will not run in linear time (although it may run in almost linear time).
Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input x belongs to a language L \in NP, with communication that is much shorter than the NP witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of proving correctness.
In this work we address this problem by constructing succinct arguments for general computations, expressed as Boolean circuits (of bounded fan-in), with a strictly linear size prover. The soundness error of the protocol is an arbitrarily small constant. Prior to this work, succinct arguments were known with a quasi-linear size prover for general Boolean circuits or with linear-size only for arithmetic circuits, defined over large finite fields.
Available from ECCC TR21-180.