Fast Reductions From RAMs to Delegatable Succinct Constraint Satisfaction Problems
Succinct arguments for NP are proof systems that allow a weak verifier to retroactively check computation done by a more powerful prover. These protocols prove membership in languages (consisting of succinctly-represented very large constraint satisfaction problems) that, alas, are unnatural in the sense that the problems that arise in practice are not in such form. For general computation tasks, the most natural and efficient representation is typically as Random-Access Machine (RAM) algorithms, because such a representation can be obtained very efficiently by applying a compiler to code written in a high-level programming language. The authors thus study efficient reductions from RAM to other problem representations for which succinct arguments are known.