Publisher： Cambridge University Press
E-ISSN： 1943-5886|62|3|981-998
ISSN： 0022-4812
Source： The Journal of Symbolic Logic, Vol.62, Iss.3, 1997-09, pp. : 981-998
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
We prove an exponential lower bound on the length of cutting plane proofs. The proof uses an extension of a lower bound for monotone circuits to circuits which compute with real numbers and use nondecreasing functions as gates. The latter result is of independent interest, since, in particular, it implies an exponential lower bound for some arithmetic circuits.
Related content
Lower bounds for cutting planes proofs with small coefficients
The Journal of Symbolic Logic, Vol. 62, Iss. 3, 1997-09 ,pp. :
Access to resources
Recommend
Lower bounds to the size of constant-depth propositional proofs
The Journal of Symbolic Logic, Vol. 59, Iss. 1, 1994-03 ,pp. :
The Journal of Symbolic Logic, Vol. 46, Iss. 2, 1981-06 ,pp. :
Convolution property and exponential bounds for symmetric monotone densities
ESAIM: Probability and Statistics, Vol. 17, Iss. issue, 2013-08 ,pp. :
Lower Bounds for Cubical Pseudomanifolds
By Klee Steven
Discrete & Computational Geometry, Vol. 46, Iss. 2, 2011-09 ,pp. :