Lower bounds for the circuit size of partially homogeneous polynomials
Hông Vân Lê
Mathematical Institute, Academy of Sciences of the Czech Republic, Czech Republic
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 which results in better lower bounds for circuit size. Our methods yield nontrivial lower bound for the circuit size of several classes of multivariate homogeneous polynomials.
|Корпоративное агентство Нидерландов
PDF file (296 kB)
Journal of Mathematical Sciences (New York), 2017, 225:4, 639–657
Hông Vân Lê, “Lower bounds for the circuit size of partially homogeneous polynomials”, Fundam. Prikl. Mat., 20:3 (2015), 153–179; J. Math. Sci., 225:4 (2017), 639–657
Citation in format AMSBIB
\paper Lower bounds for the circuit size of partially homogeneous polynomials
\jour Fundam. Prikl. Mat.
\jour J. Math. Sci.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|