Depth-3 arithmetic circuits for S(2,n)(X) and extensions of the Graham-Pollack theorem

Jaikumar Radhakrishnan, Pranab Sen and Sundar Vishwanathan

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


We consider the problem of computing the second elementary symmetric polynomial S(2,n)(X) using depth-three arithmetic circuits of the form: Sum of Products of Linear forms. 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 linear forms are allowed to have constant terms; 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 ceil(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 ceil(n/2).

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Start Conference Manager
Conference Systems