דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Hadamard Product of Polynomials and the Identity Testing Problem
event speaker icon
פושקר ג'גלקר (המכון למתמטיקה בצ'נאי, הודו)
event date icon
יום רביעי, 18.5.2011, 12:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
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.

[בחזרה לאינדקס האירועים]