Superlogarithmic-Rank Matrix Rigidity for the Walsh-Hadamard Transform

Josh Alman

For sufficiently large $N$ which is a power of 2, we prove that changing at most one percent of the entries of the $N\times N$ Walsh-Hadamard Transform cannot reduce its rank over…