Arithmetic Circuits and the Hadamard Product of Polynomials

Details Arithmetic Circuits and the Hadamard Product of Polynomials Arithmetic Circuits and the Hadamard Product of Polynomials

2009-07-23

arxiv.org/abs/0907.4006v1

Computer Science

Computational Complexity

20 pages

Scientific paper

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. 1. 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$. 2.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.

Affiliated with

Also associated with

No associations

Rating

Arithmetic Circuits and the Hadamard Product of Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Arithmetic Circuits and the Hadamard Product of Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic Circuits and the Hadamard Product of Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-354726