Depth-3 arithmetic circuits for S_n²(X) and extensions of the Graham-Pollack theorem

Abstract

We consider the problem of computing the second elementary symmetric polynomial S²_n (X) = ^Δ ∑ 1≤ i< j≤n X_iX_j using depth-three arithmetic circuits of the form ∑^r_i=1 Π^si_j=1 L_ij(X), where each L_ij is a linear form in X₁, . . . ,X_n. We consider this problem over several fields and determine exactly the number of multiplication gates required. The lower bounds are proved for inhomogeneous circuits where the L_ij's are allowed to have constants; the upper bounds are proved in the homogeneous model. For reals and rationals, the number of multiplication gates required is exactly n-1; in most other cases, it is [n/2]. This problem is related to the Graham-Pollack theorem in algebraic graph theory. In particular, our results answer the following question of Babai and Frankl: what is the minimum number of complete bipartite graphs required to cover each edge of a complete graph an odd number of times? We show that for infinitely many n, the answer is [n/2].