Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MULTI-LINEAR FUNCTIONS:
Reports tagged with multi-linear functions:
TR15-079 | 7th May 2015
Oded Goldreich, Avishay Tal

#### Matrix Rigidity of Random Toeplitz Matrices

We prove that random $n$-by-$n$ Toeplitz (alternatively Hankel) matrices over $GF(2)$ have rigidity $\Omega(\frac{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 ... more >>>

TR19-171 | 27th November 2019
Oded Goldreich

#### Improved bounds on the AN-complexity of multilinear functions

We consider arithmetic circuits with arbitrary large (multi-linear) gates for computing multi-linear functions. An adequate complexity measure for such circuits is the maximum between the arity of the gates and their number.
This model and the corresponding complexity measure were introduced by Goldreich and Wigderson (ECCC, TR13-043, 2013), ... more >>>

ISSN 1433-8092 | Imprint