Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with monotone rank:
TR12-061 | 16th May 2012
Pavel Hrubes, Amir Yehudayoff

Formulas are exponentially stronger than monotone circuits in non-commutative setting

We 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 ... more >>>

ISSN 1433-8092 | Imprint