Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Hadamard Product of Polynomials and the Identity Testing Problem
event speaker icon
Pushkar Joglekar (Institute of Mathematical Sciences, Chennai, India)
event date icon
Wednesday, 18.05.2011, 12:30
event location icon
Room 337-8 Taub Bld.
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.