The complexity of computing symmetric functions using threshold circuits
type: Item
instance of: scholarly article
title: The complexity of computing symmetric functions using threshold circuits
zbMATH Open document ID: 0780.68052
DOI: 10.1016/0304-3975(92)90372-M
author: Erik Brisson
author: Richard E. Ladner
author: Paul Beame
published in: Theoretical Computer Science
publication date: 1992-09-27T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 64925
zbMATH Keywords: size-depth tradeoffs
zbMATH Keywords: threshold circuits computing symmetric functions
zbMATH Keywords: number of connections
MaRDI profile type: Publication
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Constant Depth Reducibility
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Q3249579
cites work: Q5595902
cites work: Bounds to Complexities of Networks for Sorting and for Switching
cites work: Parallel computation with threshold functions
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: Q3762226
full work available at URL: 0304-3975(92)90372-m
OpenAlex ID: W2124321692
Recommended article: The complexity of symmetric functions in bounded-depth circuits
Recommended article: Computing Symmetric Boolean Functions by Circuits with Few Exact Threshold Gates
Recommended article: On Threshold Circuits and Polynomial Computation
Recommended article: Q3775483
Recommended article: Negation-limited circuit complexity of symmetric functions
Recommended article: New upper bounds on the Boolean circuit complexity of symmetric functions
Recommended article: Bounded-depth, polynomial-size circuits for symmetric functions
Recommended article: On the complexity of monotone circuits for threshold symmetric Boolean functions
Recommended article: Q3360126
Recommended article: Lower bounds to the complexity of symmetric Boolean functions
description: scientific article; zbMATH DE number 64925