Formulas are Exponentially Stronger than Monotone Circuits in Non-commutative Setting
Pavel Hrube, Amir Yehudayoff · 2013
We give an example of a non-commutative mono-tone polynomial f which can be computed by a polynomial-size non-commutative formula, but every monotone non-commutative circuit computing f must have an exponential size. In the non-commutative setting this gives, a fortiori, an exponential separation between monotone and general formulas, monotone and general branching programs, and monotone and general circuits. This answers some questions raised by Nisan.