Rigidity of random Toeplitz matrices with an application to depth three circuits -Tal скачать в хорошем качестве

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

Topic:Rigidity of random Toeplitz matrices with an application to depth three circuits Speaker: Avishay Tal Date:Tuesday, December 1 Joint work with Oded Goldreich. We prove that random n-by-n Toeplitz matrices over GF2 have rigidity for rank, with high probability. This improves, for r=o, over the Ω bound that is known for many explicit matrices. Our result implies that an explicit trilinear function f on n variables has complexity in the multilinear circuit model suggested by Goldreich and Wigderson, which yields an exp lower bound on the size of the so-called canonical depth-three circuits for f. For more videos go to http://www.video.ias.edu