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), and is called the AN-complexity.
The AN-complexity of a multi-linear function yields an upper bound on the size of depth-three Boolean circuits for computing the function, and it is not clear whether or not significantly smaller depth-three Boolean functions exist. Specifically, the depth-three size of Boolean circuits is at most exponential in the AN-complexity of the function. Hence, proving linear lower bounds on the AN-complexity of explicit multi-linear function is a essential step towards proving that depth-three Boolean circuits for these functions requires exponential size.
In this work we present explicit multi-linear functions that require depth-two multi-linear circuits of almost linear AN-complexity. Specifically, for every $\epsilon>0$, we show an explicit $\poly(1/\epsilon)$-linear function $f:\{0,1\}^{\poly(1/\epsilon)\cdot n}\to\{0,1\}$ such that any depth-two circuit (with general multi-linear gates) that computes $f$ must use gates of arity at least $n^{1-\epsilon}$. This improves over a corresponding lower bound of $\tildeOM(n^{2/3})$ that was known for an explicit tri-linear function (Goldreich and Tal, Computational Complexity, 2018), but leaves open the problem of showing similar AN-complexity lower bounds for multi-linear circuits of larger depth.
A key aspect in our proof is considering many (extremely skewed) random restrictions, and contrasting the sum of the values of the original function and the circuit (which supposedly computes it) taken over a (carefully chosen) subset of these random restrictions. We show that if the original circuit has too low AN-complexity, then these two sums cannot be equal, which yields a contradiction.
Additional result (17-Jan-20): For every $\epsilon>0$ and $t=O(1/\epsilon^2)$, the $\Omega(n^{1-\epsilon})$ lower bound holds also for the $t$-linear function $$f(x^{(1)},x^{(2)},...,x^{(t)}) = \sum_{i_1,...,i_{t-1}\in[n]} \left( \prod_{j\in[t-1]} x^{(j)}_{i_j} \right) \cdot x^{(t)}_{i_1+i_2+\cdots+i_{t-1}}$$