Property testing of the Boolean and binary rank

08/30/2019

∙

by   Michal Parnas, et al.

∙

0

∙

share

We present algorithms for testing if a (0,1)-matrix M has Boolean/binary rank at most d, or is ϵ-far from Boolean/binary rank d (i.e., at least an ϵ-fraction of the entries in M must be modified so that it has rank at most d). The query complexity of our testing algorithm for the Boolean rank is Õ(d^4/ ϵ^6). For the binary rank we present a testing algorithm whose query complexity is O(2^2d/ϵ). Both algorithms are 1-sided error algorithms that always accept M if it has Boolean/binary rank at most d, and reject with probability at least 2/3 if M is ϵ-far from Boolean/binary rank d.