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 >>>

Given a DNF formula $f$ on $n$ variables, the two natural size measures are the number of terms or size $s(f)$, and the maximum width of a term $w(f)$. It is folklore that short DNF formulas can be made narrow. We prove a converse, showing that narrow formulas can be ... more >>>

We explore the relationships between circuit complexity, the complexity of generating circuits, and circuit-analysis algorithms. Our results can be roughly divided into three parts:

1. Lower Bounds Against Medium-Uniform Circuits. Informally, a circuit class is ``medium uniform'' if it can be generated by an algorithmic process that is somewhat complex ... more >>>