__
Revision #1 to TR14-139 | 16th March 2015 23:05
__
#### Lower bounds for the circuit size of partially homogeneous polynomials

**Abstract:**
In this paper

we associate to each multivariate polynomial $f$ that is homogeneous relative to a subset of its variables a series of polynomial families $P_\lambda (f)$ of $m$-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in $P_\lambda (f)$ is bounded from above by the circuit size of $f$. This provides a method for obtaining lower bounds for

the circuit size of $f$ by proving $(s,r)$-(weak) elusiveness of the polynomial mapping associated with $P_\lambda (f)$. We discuss some algebraic methods for proving the $(s,r)$-(weak) elusiveness.

We also improve estimates in the normal homogeneous-form of an arithmetic circuit obtained by Raz in \cite{Raz2009} which results in better lower bounds for circuit size (Lemma \ref{lem:cor38}, Remark \ref{rem:cor38}).

Our methods yield non-trivial lower bound for the circuit size of several classes of multivariate homogeneous polynomials (Corollary \ref{cor:412}, Example \ref{ex:bi}). }

**Changes to previous version:**
Definition 3.3 of syntactic degree (p. 4) and a definition of the number $N(\Phi)$ (p.5) have been added. A missing coefficient 2 in Step 5 of the proof of Theorem 3.5 has been added and corresponding coefficients in all consequences haven been corrected.

__
TR14-139 | 31st October 2014 14:37
__

#### Lower bounds for the circuit size of partially homogeneous polynomials

**Abstract:**
In this paper

we associate to each multivariate polynomial $f$ that is homogeneous relative to a subset of its variables a series of polynomial families $P_\lambda (f)$ of $m$-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in $P_\lambda (f)$ is bounded from above by the circuit size of $f$. This provides a method for obtaining lower bounds for

the circuit size of $f$ by proving $(s,r)$-(weak) elusiveness of the polynomial mapping associated with $P_\lambda (f)$. We discuss some algebraic methods for proving the $(s,r)$-(weak) elusiveness.

We also improve estimates in the normal homogeneous-form of an arithmetic circuit obtained by Raz in \cite{Raz2009} which results in better lower bounds for circuit size (Lemma \ref{lem:cor38}, Remark \ref{rem:cor38}).

Our methods yield non-trivial lower bound for the circuit size of several classes of multivariate homogeneous polynomials (Corollary \ref{cor:412}, Example \ref{ex:bi}). }