Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MULTI-LINEAR CIRCUITS:
Reports tagged with multi-linear circuits:
TR15-079 | 7th May 2015
Oded Goldreich, Avishay Tal

#### Matrix Rigidity of Random Toeplitz Matrices

We prove that random $n$-by-$n$ Toeplitz (alternatively Hankel) matrices over $GF(2)$ have rigidity $\Omega(\frac{n^3}{r^2\log n})$ for rank $r \ge \sqrt{n}$, with high probability. This improves, for $r = o(n/\log n \log\log n)$, over the $\Omega(\frac{n^2}{r} \cdot\log(\frac{n}{r}))$ bound that is known for many explicit matrices.

Our result implies that the explicit ... more >>>

ISSN 1433-8092 | Imprint