The complexity of depth-3 circuits computing symmetric Boolean functions
type: Item
instance of: scholarly article
title: The complexity of depth-3 circuits computing symmetric Boolean functions
zbMATH Open document ID: 1185.68355
author: Guy Wolfovitz
published in: Information Processing Letters
publication date: 2010-01-29T00:00:00Z
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5664689
zbMATH Keywords: computational complexity
zbMATH Keywords: theory of computation
zbMATH Keywords: depth-3 circuits
MaRDI profile type: Publication
full work available at URL: j.ipl.2006.06.008
OpenAlex ID: W2067079998
cites work: A Boolean function requiring 3n network size
cites work: Top-down lower bounds for depth-three circuits
cites work: Which problems have strongly exponential complexity?
cites work: Q4708583
cites work: Explicit lower bound of 4.5n - o(n) for boolena circuits
cites work: Q3249579
cites work: Q4484662
cites work: An improved exponential-time algorithm for k -SAT
cites work: Exponential lower bounds for depth three Boolean circuits
cites work: Relations Among Complexity Measures
cites work: The network complexity and the Turing machine complexity of finite functions
cites work: Q4164821
DOI: 10.1016/J.IPL.2006.06.008
description: scientific article; zbMATH DE number 5664689