Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Lower bounds for the circuit size of partially homogeneous polynomials

RSS-Feed




Revision #1
Authors: Hong Van Le
Accepted on: 16th March 2015 23:05
Downloads: 346
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
Downloads: 527
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