Arithmetic Circuits and the Hadamard Product of Polynomials

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

doi:10.4230/LIPIcs.FSTTCS.2009.2304

Document

Arithmetic Circuits and the Hadamard Product of Polynomials

Authors Vikraman Arvind, Pushkar S. Joglekar, Srikanth Srinivasan

Part of: Volume: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2009-12-14

PDF

File

PDF

LIPIcs.FSTTCS.2009.2304.pdf

Filesize: 217 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2009.2304
URN: urn:nbn:de:0030-drops-23046

Subject Classification

Keywords

Hadamard product
identity testing
lower bounds
algebraic branching programs

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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}

Cite As Get BibTex

Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan. Arithmetic Circuits and the Hadamard Product of Polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 25-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2304

Author Details

Vikraman Arvind

Pushkar S. Joglekar

Srikanth Srinivasan

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail