TR16-188 Authors: Toniann Pitassi, Robert Robere

Publication: 21st November 2016 23:04

Downloads: 3597

Keywords:

For a universal constant $\alpha > 0$, we prove size lower bounds of $2^{\alpha N}$ for computing an explicit monotone function in 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 the constant factor $\alpha$. Moreover, we give one unified proof that is short and fairly elementary.