Matrix rigidity of random Toeplitz matrices
Oded Goldreich, Avishay Tal · Computational Complexity · 2016
A matrix A is said to have rigidity s for rank r if A differs from any matrix of rank r on more than s entries. We prove that random n-by-n Toeplitz matrices over $${\mathbb{F}_{2}}$$ (i.e., matrices of the form $${A_{i,j} = a_{i-j}}$$ for random bits $${a_{-(n-1)}, \ldots, a_{n-1}}$$ ) have rigidity $${\Omega(n^3/(r^2\log n))}$$ for rank $${r \ge \sqrt{n}}$$ , with high probability. This improves, for $${r = o(n/\log n \log\log n)}$$ , over the $${\Omega(\frac{n^2}{r} \cdot\log(\frac{n}{r}))}$$ bound that is known for many explicit matrices. Our result implies that the explicit trilinear $${[n]\times [n] \times [2n]}$$ function defined by $${F(x,y,z) = \sum_{i,j}{x_i y_j z_{i+j}}}$$ has complexity $${\Omega(n^{3/5})}$$ in the multilinear circuit model suggested by Goldreich and Wigderson (Electron Colloq Comput Complex 20:43, 2013), which yields an $${\exp(n^{3/5})}$$ lower bound on the size of the so-called canonical depth-three circuits for F. We also prove that F has complexity $${\tilde{\Omega}(n^{2/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 $${2^{-n}}$$ -biased distribution has complexity $${\tilde{\Omega}(n^{2/3})}$$ , regardless of depth restrictions, almost matching the known $${O(n^{2/3})}$$ upper bound for any matrix. We turn this randomized construction into an explicit 4-linear construction with similar lower bounds, using the quadratic small-biased construction of Mossel et al. (Random Struct Algorithms 29(1):56–81, 2006).