Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR01-035 | 15th April 2001 00:00

Affine Projections of Symmetric Polynomials


Authors: Amir Shpilka
Publication: 2nd May 2001 18:31
Downloads: 3583


In this paper we introduce a new model for computing=20
polynomials - a depth 2 circuit with a symmetric gate at the top=20
and plus gates at the bottom, i.e the circuit computes a=20
symmetric function in linear functions -
$S_{m}^{d}(\ell_1,\ell_2,...,\ell_m)$ ($S_{m}^{d}$ is the $d$'th=20
elementary symmetric polynomial in $m$ variables, and the=20
$\ell_i$'s are linear functions). We refer to this model as the=20
symmetric model. This new model is related to standard models=20
of arithmetic circuits, especially to depth 3 circuits.
In particular we show that in order to improve the results of
\cite{SW}, i.e to prove super-quadratic lower bounds for depth 3=20
circuits, one must first prove a super-linear lower bound for the=20
symmetric model.

We prove two nontrivial linear lower bounds for our model.
The first lower bound is for computing the determinant, and the
second is for computing the sum of two monomials.=20
The main technical contribution relates the maximal dimension=20
of linear subspaces on which $S_{m}^d$ vanishes, and lower=20
bounds to the symmetric model.
In particular we show that an answer of the following problem=20
(which is very natural, and of independent interest) will imply=20
lower bounds on symmetric circuits for many polynomials:\\

``What is the maximal dimension of a linear subspace of
${\mathcal C}^m$, on which
$S_{m}^d$ vanishes ?''\\

We give two partial solutions to the problem above, each enables=20
us to prove a different lower bound.
Using our techniques we also prove quadratic lower bounds for
depth 3 circuits computing the elementary symmetric polynomials=20
of degree $\alpha n$ (where $0< \alpha < 1$ is a constant), thus
extending the result of \cite{SW}.=20
These are the best lower bounds known
for depth 3 circuits over fields of characteristic zero.


A.~Shpilka and A.~Wigderson.
\newblock Depth-3 arithmetic formulae over=20
fields of characteristic zero.
\newblock In {\em CCC}, volume~14, pages 87--96, 1999.

ISSN 1433-8092 | Imprint