ECCC-Report TR14-139https://eccc.weizmann.ac.il/report/2014/139Comments and Revisions published for TR14-139en-usMon, 16 Mar 2015 23:05:19 +0200
Revision 1
| Lower bounds for the circuit size of partially homogeneous polynomials |
Hong Van Le
https://eccc.weizmann.ac.il/report/2014/139#revision1In 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}). }Mon, 16 Mar 2015 23:05:19 +0200https://eccc.weizmann.ac.il/report/2014/139#revision1
Paper TR14-139
| Lower bounds for the circuit size of partially homogeneous polynomials |
Hong Van Le
https://eccc.weizmann.ac.il/report/2014/139In 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}). }Sat, 01 Nov 2014 03:18:42 +0200https://eccc.weizmann.ac.il/report/2014/139