Tata Institute of Fundamental Research
Power of Subtraction in Non-commutative Models
STCS Student Seminar
Speaker:
Anamay Tengse
Organiser:
Kshitij Gajjar
Date:
Friday, 25 May 2018, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Anamay Tengse |
| Organiser: | Kshitij Gajjar |
| Date: | Friday, 25 May 2018, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.