Our next talk will take place on Wednesday, March 1st at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Josh Alman (MIT) will present joint work with Ryan Williams on “Probabilistic Rank and Matrix Rigidity”, to appear in the next STOC (abstract below).
Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
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 probabilistically approximated by low rank matrices.
Based on joint work with Ryan Williams to appear in STOC’17.