A simple lower bound for monotone clique using a communication game
type: Item
instance of: scholarly article
title: A simple lower bound for monotone clique using a communication game
zbMATH Open document ID: 0748.68029
DOI: 10.1016/0020-0190(92)90184-W
author: Mikael Goldmann
author: Johan Hastad
published in: Information Processing Letters
publication date: 1992-09-26T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 55568
zbMATH Keywords: theory of computation
zbMATH Keywords: circuit complexity
zbMATH Keywords: formula complexity
zbMATH Keywords: monotone circuit
MaRDI profile type: Publication
Wikidata QID: Q56210414
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: The monotone circuit complexity of Boolean functions
cites work: Q4726174
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Lower bounds on monotone complexity of the logical permanent
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
full work available at URL: 0020-0190(92)90184-w
OpenAlex ID: W2050688507
DBLP publication ID: journals/ipl/GoldmannH92
description: scientific article; zbMATH DE number 55568