Title: Quadratic Lower Bounds on Matrix Rigidity

Speaker: Prof Satya Lokam  (Microsoft Research)

Place: Room 1-222, FIT Building         

Time: 10:30am, Nov 16

Abstract: The rigidity of a matrix $A$ with respect to the rank bound $r$ is the minimum number of entries of $A$ that must be changed to reduce the rank of $A$ to or below $r$. It is a major unsolved problem (Valiant, 1977) to construct ``explicit" families of $n \times n$ matrices of rigidity $n^{1+\delta}$ for $r=\epsilon n$ where $\epsilon$ and $\delta$ are positive constants. In fact, no superlinear lower bounds are known for explicit families of matrices for rank bound $r=\Omega(n)$.

We will present the first optimal, $\Omega(n^2)$, lower bound on the rigidity of two ``somewhat explicit" families of matrices with respect to the rank bound $r= cn$, where $c$ is an absolute positive constant. The entries of these matrix families are (i) square roots of the first $n^2$ primes and (ii) primitive roots of unity of prime orders for the first $n^2$ primes. Our proofs use an algebraic dimension concept introduced by Shoup and Smolensky (1997) and a generalization of that concept.