Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem

Jaikumar Radhakrishnan, Pranab Sen, Sundar Vishwanathan

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 con…