Joint work with Oded Goldreich.

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

Our result implies that an explicit trilinear function f on n variables 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 canonical depth-three circuits for f.