The Taub Faculty of Computer Science Events and Talks

Motivated by the Hadamard product of matrices we define the Hadamard product of noncommutative multivariate polynomials and study its arithmetic circuit and branching program complexity. We also give applications and connections to polynomial identity testing.

One of our main results is a tight characterization of polynomial identity testing for noncommutative algebraic branching programs over the field of rationals(we show the problem is complete for logspace counting class C=L). We also study the complexity of similar identity problem for finite fields, in the case of finite fields we have slightly weaker results.

Next we consider Hadamard product of commutative multivariate polynomials and explore it's expressive power.