Linear Boolean classification, coding and "the critical problem"

Emmanuel Abbe, Noga Alon, Afonso S. Bandeira +1

The problem of constructing a minimal rank matrix over GF(2) whose kernel does not intersect a given set S is considered. In the case where S is a Hamming ball centered at 0, this…