Monotone Circuits for Connectivity Require Super-Logarithmic Depth
type: Item
instance of: scholarly article
title: Monotone Circuits for Connectivity Require Super-Logarithmic Depth
zbMATH Open document ID: 0695.94021
DOI: 10.1137/0403021
author: A. Wigderson
author: Mauricio Karchmer
published in: SIAM Journal on Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 06E30
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 4139682
zbMATH Keywords: circuit complexity
zbMATH Keywords: graph connectivity
zbMATH Keywords: complexity of Boolean functions
zbMATH Keywords: monotone circuit
zbMATH Keywords: undirected graph
zbMATH Keywords: communication complexity
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1137/0403021
OpenAlex ID: W2049016755
description: scientific article