Monotone circuit lower bounds from resolution

DOI10.1145/3188745.3188838zbMath1428.68151OpenAlexW2809677183MaRDI QIDQ5230347

No author found.

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: http://infoscience.epfl.ch/record/282317

zbMATH Keywords

circuit complexityproof complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (8)

Adventures in monotone complexity and TFNP ⋮ Short Proofs Are Hard to Find ⋮ Lifting Theorems for Equality ⋮ Query-To-Communication Lifting for BPP Using Inner Product ⋮ Unnamed Item ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Reflections on Proof Complexity and Counting Principles ⋮ Large clique is hard on average for resolution

This page was built for publication: Monotone circuit lower bounds from resolution