Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR14-139 | 16th March 2015 23:05

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

Revision #1
Authors: Hong Van Le
Accepted on: 16th March 2015 23:05
Keywords:

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.

### Paper:

TR14-139 | 31st October 2014 14:37

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

TR14-139
Authors: Hong Van Le
Publication: 1st November 2014 03:18
Keywords:

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}). }

ISSN 1433-8092 | Imprint