演讲人： Satya Lokam Microsoft Research
时间： 2005-11-16 10:30-2005-11-16 11:30
地点：FIT-1-222
内容：

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.