Rigidity of random Toeplitz matrices with an application to depth three circuits

 Computer Science/Discrete Mathematics Seminar II Topic: Rigidity of random Toeplitz matrices with an application to depth three circuits Speaker: Avishay Tal Affiliation: Member, School of Mathematics Date: Tuesday, December 1 Time/Room: 10:30am - 12:30pm/S-101 Video Link: https://video.ias.edu/csdm/2015/1201-Tal

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) \cdot \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$.