Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes

DOI10.1016/S0020-0190(98)00079-9zbMath1339.03053OpenAlexW2071159099MaRDI QIDQ293309

Jan Johannsen

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098000799?np=y

zbMATH Keywords

computational complexitycutting planes proofcommunication complexitymonotone circuit

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cites Work

• Monotone real circuits are more powerful than monotone Boolean circuits
• On the complexity of cutting-plane proofs
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• Lower bounds for cutting planes proofs with small coefficients
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes