Abstract
In this paper we describe a new technique for obtaining lower bounds on restricted classes of non-monotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate polynomials, based on the linear span of their partial derivatives. We use the technique to obtain new lower bounds for computing symmetric polynomials and iterated matrix products.
Introduction
Proving lower bounds in computational complexity—demonstrating that a problem cannot be solved within certain resource constraints—is one of the most challenging tasks in theoretical computer science. While upper bounds are established by providing an algorithm, lower bounds require proving a negative across all possible algorithms or circuits.
In their seminal 1995 work, Noam Nisan and Avi Wigderson address this challenge within the realm of arithmetic circuits. These circuits compute polynomials using only addition and multiplication gates. Unlike Boolean circuits, arithmetic circuits are particularly difficult to analyze when they are "non-monotone"—meaning they can use subtraction or negative constants. In such cases, terms can cancel out, making simple counting arguments ineffective. This paper introduces a powerful complexity measure based on partial derivatives to overcome these hurdles for several restricted classes of circuits.
The Partial Derivative Complexity Measure
The central innovation of the paper is a complexity measure for a multivariate polynomial $f$, defined as the dimension of the linear space spanned by all its partial derivatives of all orders. Let $\partial(f)$ denote the set of all partial derivatives of $f$. The measure is defined as:
$$\text{dim}(\text{span}(\partial(f)))$$
This measure serves as a proxy for the "richness" or "complexity" of a polynomial. The authors utilize a "bottleneck" argument to prove lower bounds:
- Circuit Limitation: They demonstrate that for specific circuit architectures (e.g., shallow or homogeneous circuits), the dimension of the partial derivative space cannot increase rapidly from the inputs to the output.
- Function Complexity: They identify target functions, such as elementary symmetric polynomials, that naturally possess a very high-dimensional partial derivative space.
- The Contradiction: If a small or shallow circuit of the restricted type were to compute such a function, it would imply a growth in the derivative space dimension that exceeds the circuit's structural capacity.
For more sophisticated models like multilinear circuits, the authors augment this approach with random restrictions. By fixing a subset of variables to constants, they simplify the circuit's structure while ensuring the remaining polynomial retains high complexity, allowing the partial derivative measure to remain effective.
Key Results and Benchmarks
The paper applies this technique to several fundamental mathematical problems, establishing significant lower bounds:
1. Elementary Symmetric Polynomials ($SYM^n_d$)
The $d$-th elementary symmetric polynomial in $n$ variables is the sum of all products of $d$ distinct variables. The authors prove that any homogeneous depth-3 circuit computing $SYM^n_d$ requires a size of at least:
$$\Omega\left(\left(\frac{n}{2d}\right)^{d/2}\right)$$
This provides an exponential lower bound for a wide range of $d$.
2. Iterated Matrix Multiplication ($IMM^n_d$)
Computing the product of $d$ matrices of size $n \times n$ is a central problem in algebraic complexity. The paper shows that for homogeneous depth-3 circuits, computing the $(1,1)$-entry of the product requires size:
$$\Omega\left(\frac{n^{d-1}}{d!}\right)$$
3. Multilinear and Pure Circuits
The authors also investigate multilinear circuits, where every gate computes a multilinear polynomial. They achieve a depth lower bound of $\Omega(\log d / \log \log d)$ for general multilinear circuits computing the product of $2 \times 2$ matrices. For the more restricted class of "pure" multilinear circuits (where variable sets of sub-circuits are either nested or disjoint), they achieve a tight lower bound of $\Omega(\log n \log d)$.
Discussion and Open Problems
While the partial derivative technique is highly effective for restricted circuit classes, extending it to unrestricted (general) arithmetic circuits remains a major open challenge. General circuits can reuse intermediate computations in ways that bypass the limitations of homogeneous or multilinear structures.
The authors highlight the "Ben-Or" problem: finding an explicit function that cannot be computed by a polynomial-size, depth-3 circuit with unbounded fan-in. Despite the progress made in this paper, this specific problem remains unsolved and continues to be a significant goal in the field.
Conclusion
Nisan and Wigderson's use of partial derivatives provided a new lens through which to view algebraic complexity. By linking the geometric/algebraic properties of a polynomial (its derivatives) to the structural requirements of the circuits that compute it, they established a framework that has influenced decades of subsequent research in lower bounds.
Summary updated