ECCC-Report TR16-188https://eccc.weizmann.ac.il/report/2016/188Comments and Revisions published for TR16-188en-usMon, 21 Nov 2016 23:04:02 +0200
Paper TR16-188
| Strongly Exponential Lower Bounds for Monotone Computation |
Toniann Pitassi,
Robert Robere
https://eccc.weizmann.ac.il/report/2016/188For 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.
Mon, 21 Nov 2016 23:04:02 +0200https://eccc.weizmann.ac.il/report/2016/188