Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR12-061 | 16th May 2012 10:35

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

TR12-061
Authors: Pavel Hrubes, Amir Yehudayoff
Publication: 16th May 2012 10:43
Downloads: 211583
Keywords:

Abstract:

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 branching programs, and monotone and general circuits. This answers some questions raised in \cite{Nisan}.

ISSN 1433-8092 | Imprint