Surprisingly, for a larger number of colors, the number of guesses needed to reconstruct the codeword has remained unknown. In particular, for \(k=n\) , the best known algorithm, by Doerr, Doerr, Spöhel, and Thomas [1]}, reconstructs the codeword in \(\mathcal {O}(n \log \log n)\)  guesses, whereas no significant improvement on the information theoretic lower bound of \(\Omega (n)\)  is known.
