• The Geometry of Matrix Rigidity 

      Landsberg, J. M.; Taylor, Jacob; Vishnoi, Nisheeth Kumar (Georgia Institute of Technology, 2003)
      Consider the following problem: Given an n×n matrix A and an input x, compute Ax. This problem has a simple algorithm which runs in time O(n²). The question thus is: Is this is the best possible ? Valiant showed ([12]) ...