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$.