Abstract
Given oracle access to some string w, we would like to verify (using few queries,
with the aid of an interactive prover), that w is a codeword of the Reed-Solomon code.
An ingenious FFT-based protocol called FRI (Fast Reed-Solomon IOPP)
with low (and practical) complexity for both prover and verifier was recently given by [BBHR]. Follow-up work of [BKS] showed that FRI
rejects any w that is very far from the Reed-Solomon code with quite large probability.
* We give an improved (and tight) analysis for the soundness of FRI.
* We then give a new protocol called *DEEP-FRI* which has both (a) a better name, and
(b) further improved (and possibly optimal) soundness for this problem. It is based on querying
the polynomial outside the domain where it was initially evaluated.
* Finally we use this out-of-domain-sampling idea to improve the soundness of STARK proofs for
general computation.
Based on joint work with Eli Ben-Sasson, Lior Goldberg, and Shubhangi Saraf