Property testing of the Boolean and binary rank

Michal Parnas, Dana Ron, Adi Shraibman

We present algorithms for testing if a $(0,1)$-matrix $M$ has Boolean/binary rank at most $d$, or is $\epsilon$-far from Boolean/binary rank $d$ (i.e., at least an $\epsilon$-fraction of the ent…