Computer Science – Discrete Mathematics
Scientific paper
2001-10-16
Computer Science
Discrete Mathematics
30 pages. 1 figure. A preliminary version appeared in FSTTCS 2000. This is the full version of that paper
Scientific paper
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 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 \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}.
Radhakrishnan Jaikumar
Sen Pranab
Vishwanathan Sundar
No associations
LandOfFree
Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-695