License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2304
URN: urn:nbn:de:0030-drops-23046
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2304/
Go to the corresponding LIPIcs Volume Portal

Arvind, Vikraman ; Joglekar, Pushkar S. ; Srinivasan, Srikanth

Arithmetic Circuits and the Hadamard Product of Polynomials

pdf-format:
09005.ArvindA.2304.pdf (0.2 MB)

Abstract

Motivated by the Hadamard product of matrices we define the Hadamard
product of multivariate polynomials and study its arithmetic circuit
and branching program complexity. We also give applications and
connections to polynomial identity testing. Our main results are
the following.
\begin{itemize}
\item[$\bullet$] We show that noncommutative polynomial identity testing for
algebraic branching programs over rationals is complete for
the logspace counting class $\ceql$, and over fields of characteristic
$p$ the problem is in $\ModpL/\Poly$.
\item[$\bullet$] We show an exponential lower bound for expressing the
Raz-Yehudayoff polynomial as the Hadamard product of two monotone
multilinear polynomials. In contrast the Permanent can be expressed
as the Hadamard product of two monotone multilinear formulas of
quadratic size.
\end{itemize}

BibTeX - Entry

@InProceedings{arvind_et_al:LIPIcs:2009:2304,
  author =	{Vikraman Arvind and Pushkar S. Joglekar and Srikanth Srinivasan},
  title =	{{Arithmetic Circuits and the Hadamard Product of Polynomials}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{25--36},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Ravi Kannan and K. Narayan Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2304},
  URN =		{urn:nbn:de:0030-drops-23046},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2304},
  annote =	{Keywords: Hadamard product, identity testing, lower bounds, algebraic branching programs}
}

Keywords: Hadamard product, identity testing, lower bounds, algebraic branching programs
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2009
Date of publication: 14.12.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI