Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-061 | 16th May 2012 10:35

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

RSS-Feed




TR12-061
Authors: Pavel Hrubes, Amir Yehudayoff
Publication: 16th May 2012 10:43
Downloads: 210165
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