  In this work, we construct the first locally-correctable codes (LCCs), and
locally-testable codes (LTCs) with constant rate, constant relative distance,
and sub-polynomial query complexity. Specifically, we show that there exist
binary LCCs and LTCs with block length $n$, constant rate (which can even be
taken arbitrarily close to 1), constant relative distance, and query complexity
$\exp(\tilde{O}(\sqrt{\log n}))$. Previously such codes were known to exist
only with $\Omega(n^{\beta})$ query complexity (for constant $\beta > 0$), and
there were several, quite different, constructions known.
  Our codes are based on a general distance-amplification method of Alon and
Luby~\cite{AL96_codes}. We show that this method interacts well with local
correctors and testers, and obtain our main results by applying it to suitably
constructed LCCs and LTCs in the non-standard regime of \emph{sub-constant
relative distance}.
  Along the way, we also construct LCCs and LTCs over large alphabets, with the
same query complexity $\exp(\tilde{O}(\sqrt{\log n}))$, which additionally have
the property of approaching the Singleton bound: they have almost the
best-possible relationship between their rate and distance. This has the
surprising consequence that asking for a large alphabet error-correcting code
to further be an LCC or LTC with $\exp(\tilde{O}(\sqrt{\log n}))$ query
complexity does not require any sacrifice in terms of rate and distance! Such a
result was previously not known for any $o(n)$ query complexity.
  Our results on LCCs also immediately give locally-decodable codes (LDCs) with
the same parameters.
