A note on monotone real circuits

DOI10.1016/j.ipl.2017.11.002zbMath1422.68115OpenAlexW2768379587MaRDI QIDQ1685020

Pavel Pudlák, Pavel Hrubeš

Publication date: 13 December 2017

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.11.002

zbMATH Keywords

computational complexityKarchmer-Wigderson gamemonotone real circuit

Mathematics Subject Classification ID

Related Items (4)

Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ Unnamed Item ⋮ On semantic cutting planes with very small coefficients ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exponential lower bound for the size of monotone real circuits
• Dag-like communication and its applications
• On extracting computations from propositional proofs (a survey).
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Interpolation by a Game
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Semantic Versus Syntactic Cutting Planes
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic

This page was built for publication: A note on monotone real circuits