Probabilistically Checkable Proofs (PCPs) [Babai et al. FOCS 90; Arora et al. JACM 98] can be used to construct asymptotically efficient cryptographic zero knowledge arguments of membership in any language in NEXP, with minimal communication complexity and computational effort on behalf of both prover and verifier [Babai et al. STOC ... more >>>

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are $\delta$-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are $\delta$-close to the property. In particular, no set ... more >>>

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 ... more >>>

Concretely efficient interactive oracle proofs (IOPs) are of interest due to their applications to scaling blockchains, their minimal security assumptions, and their potential future-proof resistance to quantum attacks.

Scalable IOPs, in which prover time scales quasilinearly with the computation size and verifier time scales poly-logarithmically with it, have been known ... more >>>