We consider a special variant of Clustering Aggregation, which asks for a binary string that minimizes the Mirkin distance to some input binary strings of equal length. The problem is known to be NP-hard under Turing reduction  . We strengthen this result by providing a polynomial-time many-one reduction. Unless ETH fails, no -time algorithm exists for our problem instances with being the length of the input strings.
Generally speaking, the Mirkin distance of two strings s and s’ counts the disagreements of s and s’ for each pair of columns.
 On the parameterized complexity of consensus clustering, by M. Dörnfelder and J. Guo and C. Komusiewicz and M. Weller.
Our paper can be found on arXiv.