### DIMACS Theoretical Computer Science Seminar

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