## Matrix Rigidity of Random Toeplitz Matrices

#### Webpage for a paper by Oded Goldreich and Avishay Tal

#### Abstract

We prove that random $n$-by-$n$ Toeplitz (alternatively Hankel) matrices
over $F_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 trilinear $[n]\times [n] \times [2n]$
function defined by $F(x,y,z) = \sum_{i,j}{x_i y_j z_{i+j}}$
has complexity $\Omega(n^{3/5})$ in the multilinear circuit model
suggested by Goldreich and Wigderson (ECCC, 2013),
which yields an $\exp(n^{3/5})$ lower bound on the size
of the so-called \emph{canonical} depth-three circuits for $F$.
We also prove that $F$ has complexity $\tilde{\Omega}(n^{2/3})$
if the multilinear circuits are further restricted to be of depth $2$.

In addition, we show that a matrix whose entries are sampled from
a $2^{-n}$-biased distribution has complexity $\tilde{\Omega}(n^{2/3})$,
regardless of depth restrictions, almost matching the $O(n^{2/3})$
upper bound for any matrix by Goldreich and Wigderson.
We turn this randomized construction into an explicit 4-linear construction
with similar lower bounds, using the quadratic small-biased construction
of Mossel et al. (RS&A, 2006).

#### Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.