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