Lower Bounds on Matrix Rigidity via a Quantum Argument

Ronald de Wolf

The rigidity of a matrix measures how many of its entries need to be changed in order to reduce its rank to some value. Good lower bounds on the rigidity of an explicit matrix woul…