TCS+ Talk

A matrix M is called rigid if M has 'high' rank, and one needs to change 'many' entries of M before it has 'low' rank. Matrix rigidity was introduced by Leslie Valiant in 1977, as a path towards proving arithmetic circuit lower bounds. In order to prove such a bound, one needs to give an explicit rigid matrix (for certain appropriate rigidity parameters). The problem of finding such an explicit rigid matrix is still open. One family of matrices which was conjectured to be rigid is the Walsh-Hadamard transform (a.k.a. Sylvester matrices, a.k.a. the communication matrix of Inner Product modulo 2). I will present a proof that the Walsh-Hadamard transform is, in fact, not sufficiently rigid for Valiant's program. Our proof uses a connection from recent "polynomial method" algorithms between low rank matrices and low degree polynomials. I will also discuss a natural notion we call the probabilistic rank of a matrix, which measures the extent to which a matrix can be probabilistical​ly approximated by low rank matrices. Based on joint work with Ryan Williams to appear in STOC'17.