  Motivated by the quest for scalable and succinct zero knowledge arguments, we
revisit worst-case-to-average-case reductions for linear spaces, raised by
[Rothblum, Vadhan, Wigderson, STOC 2013]. We first show a sharp quantitative
form of a theorem which says that if an affine space $U$ is $\delta$-far in
relative Hamming distance from a linear code $V$ - this is the worst-case
assumption - then most elements of $U$ are almost $\delta$-far from $V$ - this
is the average case. This leads to an optimal analysis of the soundness of the
FRI protocol of [Ben-Sasson, et.al., eprint 2018] for proving proximity to
Reed-Solomon codes.
  To further improve soundness, we sample outside the box. We suggest a new
protocol which asks a prover for values of a polynomial at points outside the
domain of evaluation of the Reed-Solomon code. We call this technique Domain
Extending for Eliminating Pretenders (DEEP).
  We use the DEEP technique to devise two new protocols: (1) An Interactive
Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. This soundness
of the protocol improves upon that of the FRI protocol while retaining linear
arithmetic proving complexity and logarithmic verifier arithmetic complexity.
(2) An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI)
protocol used to construct zero knowledge scalable transparent arguments of
knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol,
called DEEP-ALI, improves soundness of this crucial step from a small constant
$< 1/8$ to a constant arbitrarily close to $1$.
