Title: Rigidity of Random Toeplitz Matrices with an Application to Depth Three Circuits
Speaker: Avishay Tal, IAS
Date: Wednesday, December 2, 2015 11:00am-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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.
Joint work with Oded Goldreich.
See: https://dragon.rutgers.edu/~mk1029/theoryseminarF15.html