We provide a number of algorithmic results for the following family of problems: For a given binary m × n matrix A and a nonnegative integer k, decide whether there is a “simple” binary matrix B which di ers from A in at most k entries. For an integer r, the “simplicity” of B is characterized as follows. Binary r-Means: Matrix B has at most r di erent columns. This problem is known to be NP-complete already for r = 2. We show that the problem is solvable in time 2O(k log k) · (nm)O (1) and thus is fixed-parameter tractable parameterized by k. We also complement this result by showing that when being parameterized by r and k, the problem admits an algorithm of running time 2O(r 3/2·k log k)(nm)O (1), which is subexponential in k for r ∈ o((k/log k)1/3). Low GF(2)-Rank Approximation: Matrix B is of GF(2)-rank at most r. This problem is known to be NP-complete already for r = 1. It is also known to be W[1]-hard when parameterized by k. Interestingly, when parameterized by r and k, the problem is not only fixed-parameter tractable, but it is solvable in time 2O(r 3/2·k log k)(nm)O (1), which is subexponential in k for r ∈ o((k/log k)1/3). Low Boolean-Rank Approximation: Matrix B is of Boolean rank at most r. The problem is known to be NP-complete for k = 0 as well as for r = 1. We show that it is solvable in subexponential in k time 2O(r2r·k log k)(nm)O (1). © Fedor V. Fomin, Petr A. Golovach, and Fahad Panolan;.