{
"type": "report",
"id": "https://doi.org/10.4230/lipics.fsttcs.2009.2304",
"categories": [
"Computer Science",
"000 Computer science, knowledge, general works"
],
"language": "eng",
"author": [
{
"family": "Arvind",
"given": "Vikraman"
},
{
"family": "Joglekar",
"given": "Pushkar S."
},
{
"family": "Srinivasan",
"given": "Srikanth"
}
],
"issued": {
"date-parts": [
[
2009
]
]
},
"abstract": "Motivated by the Hadamard product of matrices we define the Hadamard\n product of multivariate polynomials and study its arithmetic circuit\n and branching program complexity. We also give applications and\n connections to polynomial identity testing. Our main results are\nthe following.\n\\begin{itemize}\n\\item[$\\bullet$] We show that noncommutative polynomial identity testing for\n algebraic branching programs over rationals is complete for\nthe logspace counting class $\\ceql$, and over fields of characteristic\n$p$ the problem is in $\\ModpL/\\Poly$.\n\\item[$\\bullet$] We show an exponential lower bound for expressing the\n Raz-Yehudayoff polynomial as the Hadamard product of two monotone\n multilinear polynomials. In contrast the Permanent can be expressed\n as the Hadamard product of two monotone multilinear formulas of\n quadratic size.\n\\end{itemize}",
"DOI": "10.4230/lipics.fsttcs.2009.2304",
"page": "-",
"publisher": "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany",
"title": "Arithmetic Circuits and the Hadamard Product of Polynomials",
"version": "1.0"
}