A simple lower bound for monotone clique using a communication game

DOI10.1016/0020-0190(92)90184-WzbMath0748.68029OpenAlexW2050688507WikidataQ56210414 ScholiaQ56210414MaRDI QIDQ1190521

Mikael Goldmann, Johan T. Håstad

Publication date: 26 September 1992

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

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90184-w

zbMATH Keywords

circuit complexitytheory of computationformula complexitymonotone circuit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Communication Lower Bounds via Critical Block Sensitivity, Clique problem, cutting plane proofs and communication complexity, Ehrenfeucht-Fraïssé Games on Random Structures, The maximum clique problem

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Lower bounds on monotone complexity of the logical permanent
• The monotone circuit complexity of Boolean functions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Parity, circuits, and the polynomial-time hierarchy
• Unnamed Item