Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-188 | 21st November 2016 22:41

Strongly Exponential Lower Bounds for Monotone Computation

RSS-Feed




TR16-188
Authors: Toniann Pitassi, Robert Robere
Publication: 21st November 2016 23:04
Downloads: 4003
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint