We prove that random n -by- n Toeplitz (alternatively Hankel) matrices over G F (2) have rigidity ( n 3 r 2 log n ) for rank r n , with high probability. This improves, for r = o ( n log n log log n ) , over the ( r n 2 log ( r n )) bound that is known for many explicit matrices.

Our result implies that the explicit trilinear [ n ] [ n ] [ 2 n ] function defined by F ( x y z ) = i j x i y j z i + j has complexity ( 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 \emph{canonical} depth-three circuits for F . We also prove that F has complexity ( 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 ( n 2 3 ) , regardless of depth restrictions, almost matching the O ( n 2 3 ) upper bound for any matrix by Goldreich and Wigderson. 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.~(RS\&A, 2006).