Authors
Oded Goldreich, Avishay Tal
Publication date
2016/6/19
Book
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
Pages
91-104
Description
We prove that random n-by-n Toeplitz (alternatively Hankel) matrices over F2 have rigidity Ω(n3/r2logn) for rank r ≥ √n, with high probability. For r = o(n/logn · loglogn), this improves over the Ω(n2/r · log(n/r)) bound that is known for many explicit matrices.
Our result implies that the explicit trilinear [n]× [n] × [2n] function defined by F(x,y,z) = ∑i,jxi yj zi+j has complexity Ω(n3/5) in the multilinear circuit model suggested by Goldreich and Wigderson (ECCC, 2013), which yields an exp(n3/5) lower bound on the size of the so-called canonical depth-three circuits for F. We also prove that F has complexity Ω(n2/3) if the multilinear circuits are further restricted to be of depth 2.
In addition, we show that a matrix whose entries are sampled from a 2n-biased distribution has complexity Ω(n2/3), regardless of depth restrictions, almost matching the known O(n2/3) upper bound for any matrix. We turn this randomized construction …
Total citations
2016201720182019202020212022202326166135
Scholar articles
O Goldreich, A Tal - Proceedings of the forty-eighth annual ACM …, 2016