An exponential lower bound for the size of monotone real circuits
type: Item
instance of: scholarly article
title: An exponential lower bound for the size of monotone real circuits
zbMATH Open document ID: 0922.68065
author: Armin Haken
author: Stephen Cook
published in: Journal of Computer and System Sciences
publication date: 1999-05-11T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1286246
zbMATH Keywords: unrestricted cutting plane proofs
MaRDI profile type: Publication
full work available at URL: jcss.1998.1617
OpenAlex ID: W2083193613
cites work: The monotone circuit complexity of Boolean functions
cites work: Q4726174
cites work: Q4234107
cites work: Q4385519
cites work: Many hard examples for resolution
cites work: On the complexity of cutting-plane proofs
cites work: The intractability of resolution
cites work: Q4231908
cites work: Lower bounds for resolution and cutting plane proofs and monotone computations
cites work: Q3758729
cites work: Hard examples for resolution
cites work: Q3762226
DOI: 10.1006/JCSS.1998.1617
Recommended article: Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
Recommended article: Strongly exponential lower bounds for monotone computation
Recommended article: A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
Recommended article: Lower bounds on monotone arithmetic circuits with restricted depths
Recommended article: Lower bounds for monotone counting circuits
Recommended article: Lower bounds for monotone \(q\)-multilinear Boolean circuits
Recommended article: A direct version of Shamir and Snir's lower bounds on monotone circuit depth
Recommended article: The monotone circuit complexity of Boolean functions
Recommended article: A lower bound for monotone arithmetic circuits computing \(0-1\) permanent
Recommended article: Q3758729
description: scientific article; zbMATH DE number 1286246