  We investigate the complexity of embeddings between bi-embeddable structures.
In analogy with categoricity spectra, we define the bi-embeddable categoricity
spectrum of a structure $\mathcal A$ as the family of Turing degrees that
compute embeddings between any computable bi-embeddable copies of $\mathcal A$;
the degree of bi-embeddable categoricity of $\mathcal A$ is the least degree in
this spectrum (if it exists). We extend many known results about categoricity
spectra to the case of bi-embeddability. In particular, we exhibit structures
without degree of bi-embeddable categoricity, and we show that every degree
d.c.e. above $\mathbf{0}^{(\alpha)}$ for $\alpha$ a computable successor
ordinal and $\mathbf{0}^{(\lambda)}$ for $\lambda$ a computable limit ordinal
is a degree of bi-embeddable categoricity. We also give examples of families of
degrees that are not bi-embeddable categoricity spectra.
