Property testing of the Boolean and binary rank.
2019
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 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 $\tilde{O}\left(d^4/ \epsilon^6\right)$. For the binary rank we present a testing algorithm whose query complexity is $O(2^{2d}/\epsilon)$.
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 $\epsilon$-far from Boolean/binary rank $d$.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
17
References
0
Citations
NaN
KQI