Algorithmic Aspects on the Construction of Separating Codes

In this paper, we discuss algorithmic aspects of separating codes, that is, codes where any two subsets (of a specified size) of their code words have at least one position with distinct elements. More precisely we focus on the (non trivial) case of binary 2-separating codes. Firstly, we use the Lovasz Local Lemma to obtain a lower bound on the existence of such codes that matches the previously best known lower bound. Then, we use the algorithmic version of the Lovasz Local Lemma to construct such codes and discuss its implications regarding computational complexity. Finally, we obtain explicit separating codes, with computational complexity polynomial in the length of the code and with rate larger than the well-known Simplex code.