Radhakrishnan, Jaikumar ; Sen, Pranab ; Vishwanathan, Sundar (2000) Depth3 arithmetic circuits for S_{n}^{2}(X) and extensions of the GrahamPollack theorem Lecture Notes in Computer Science, 1974 . pp. 176187. ISSN 03029743

PDF
 Author Version
299kB 
Official URL: http://www.springerlink.com/content/l3u8tn6914gl4a...
Related URL: http://dx.doi.org/10.1007/3540444505_14
Abstract
We consider the problem of computing the second elementary symmetric polynomial S^{2}_{n} (X) = ^{Δ} ∑ 1≤ i< j≤n X_{i}X_{j} using depththree arithmetic circuits of the form ∑^{r}_{i=1} Π^{si}_{j=1} L_{ij}(X), where each L_{ij} is a linear form in X_{1}, . . . ,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 n1; in most other cases, it is [n/2]. This problem is related to the GrahamPollack 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].
Item Type:  Article 

Source:  Copyright of this article belongs to Springer. 
ID Code:  89516 
Deposited On:  27 Apr 2012 13:36 
Last Modified:  19 May 2016 04:03 
Repository Staff Only: item control page