  We introduce a notion of \emph{efficient stability} for finite presentations
of groups. Informally, a finite presentation using generators $S$ and relations
$R$ is \emph{stable} if any map from $S$ to unitaries that approximately
satisfies the relations (in the tracial norm) is close to the restriction of a
representation of $G$ to the subset $S$. This notion and variants thereof have
been extensively studied in recent years, in part motivated by connections to
property testing in computer science. The novelty in our work is the focus on
\emph{efficiency}, which, informally, places an onus on small presentations --
in the sense of encoding length. The goal in this setup is to achieve
non-trivial tradeoffs between the presentation length and its modulus of
stability.
  With this goal in mind we analyze various natural examples of presentations.
We provide a general method for constructing presentations of $\mathbb{Z}_2^k$
from linear error-correcting codes. We observe that the resulting presentation
has a weak form of stability exactly when the code is \emph{testable}. This
raises the question of whether testable codes give rise to genuinely stable
presentations using this method. While we cannot show that this is the case in
general, we leverage recent results in the study of non-local games in quantum
information theory (Ji et al., Discrete Analysis 2021) to show that a specific
instantiation of our construction, based on the Reed-Muller family of codes,
leads to a stable presentation of $\mathbb{Z}_2^k$ of size polylog$(k)$ only.
As an application, we combine this result with recent work of de la Salle
(arXiv:2204.07084) to re-derive the quantum low-degree test of Natarajan and
Vidick (IEEE FOCS'18), which is a key building block in the recent refutation
of Connes' Embedding Problem via complexity theory (Ji et al.,
arXiv:2001.04383).
