  Wireless communication is enabling billions of people to connect to each
other and the internet, transforming every sector of the economy, and building
the foundations for powerful new technologies that hold great promise to
improve lives at an unprecedented rate and scale. The rapid increase in the
number of devices and the associated demands for higher data rates and broader
network coverage fuels the need for more robust wireless technologies. The key
technology identified to address this problem is referred to as Cell-Free
Massive MIMO (CF-mMIMO). CF-mMIMO is accompanied by many challenges, one of
which is efficiently allocating limited resources. In this paper, we focus on a
major resource allocation problem in wireless networks, namely the Pilot
Assignment problem (PA). We show that PA is strongly NP-hard and that it does
not admit a polynomial-time constant-factor approximation algorithm. Further,
we show that PA cannot be approximated in polynomial time within
$\mathcal{O}(K^2)$ (where $K$ is the number of users) when the system consists
of at least three pilots. Finally, we present an approximation lower bound of
$1.058$ (resp. $\epsilon|K|^2$, for $\epsilon >0$) in special cases where the
system consists of exactly two (resp. three) pilots.
