Strongly exponential lower bounds for monotone computation

For a universal constant α > 0 we prove size lower bounds of 2 α( n ) for an explicit function in monotone NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where n is the number of variables of the underlying function. Our lower bounds improve on the best previous bounds in each of these models, and are the best possible for any function up to constant factors in the exponent. Moreover, we give one unified proof that is short and fairly elementary.

Authors

• Toniann Pitassi
• Robert Robere

Keywords

• circuit complexity
• comparator circuits
• formulas
• monotone complexity
• rank method
• span programs
• switching networks