Matrix Rigidity

SHORT TALKS BY POSTDOCTORAL MEMBERS
Topic:Matrix Rigidity
Speaker:Zeev Dvir
Affiliation:Member, School of Mathematics
Date:Thursday, September 24
Time/Room:2:00pm - 3:00pm/S-101

A rigid matrix is a matrix that cannot be represented as the sum of a low rank matrix and a sparse matrix. Constructing explicit rigid matrices (for certain parameters of rank and sparsity) is a long standing open problem with applications to circuit lower bounds. In the talk I will present several different formulations of this problem.