School of Technology and Computer Science Seminars
Power of Subtraction in Non-commutative Models
by Anamay Tengse (School of Technology and Computer Science, TIFR)
Friday, May 25, 2018
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
Non-commutative algebraic circuits are those in which the variables do not commute under multiplication. Additionally, a circuit is called monotone if it does not use subtractions or negative constants. Circuits are known to be exponentially more powerful than formulas, in the non-commutative case as well as in the monotone non-commutative case. In this talk, we will see a result of Hrubes and Yehudayoff showing a non-commutative polynomial that has small non-monotone formulas (weakest non-monotone models), but requires exponentially large monotone circuits (strongest monotone models), in the non-commutative setting. No background to algebraic circuits will be assumed. |