Abstract: The k-undercover Boolean Matrix Factorization problem aims at approximating an (m×n) Boolean matrix X as the Boolean product of an (m×k) and a (k×n) matrices A ◦ B such that X is a cover of A ◦ B, i.e., no representation error is allowed on the 0’s entries of the matrix X. In this paper, we propose two exact methods based on MaxSAT encodings to infer optimal and “block-optimal” k-undercover. From a theoretical standpoint, we prove that our method of inferring “block-optimal” k-undercover is a (1−1/e)-approximation for the optimal k-undercover problem, and from a practical standpoint, experimental results show that our “block-optimal” k-undercover algorithm outperforms the state of the art even when compared with algorithms for the more general k-undercover Boolean Matrix Factorization problem for which only minimizing reconstruction error is required.