Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR19-171 | 16th January 2020 23:48

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

Revision #2
Authors: Oded Goldreich
Accepted on: 16th January 2020 23:48
Keywords:

Abstract:

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.

For every $\epsilon>0$ and $t=O(1/\epsilon^2)$, the $\Omega(n^{1-\e})$ 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}}$$

Changes to previous version:

Added a new result (see Thm 1.8), which is proved in the new Section 3.

Revision #1 to TR19-171 | 9th January 2020 22:21

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

Revision #1
Authors: Oded Goldreich
Accepted on: 9th January 2020 22:21
Keywords:

Abstract:

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.

Changes to previous version:

Correcting some typos, and adding a comment (just after Thm 1.7).

### Paper:

TR19-171 | 27th November 2019 16:53

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

TR19-171
Authors: Oded Goldreich
Publication: 27th November 2019 16:53
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint