ECCC-Report TR12-061https://eccc.weizmann.ac.il/report/2012/061Comments and Revisions published for TR12-061en-usWed, 16 May 2012 10:43:31 +0300
Paper TR12-061
| Formulas are exponentially stronger than monotone circuits in non-commutative setting |
Pavel Hrubes,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2012/061We give an example of a non-commutative monotone 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 in \cite{Nisan}.
Wed, 16 May 2012 10:43:31 +0300https://eccc.weizmann.ac.il/report/2012/061