Upper and lower bounds for some depth-3 circuit classes
type: Item
instance of: scholarly article
title: Upper and lower bounds for some depth-3 circuit classes
zbMATH Open document ID: 0890.68063
DOI: 10.1007/BF01294257
author: Richard Beigel
author: Alexis Maciel
published in: Computational Complexity
publication date: 1998-07-06T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1109555
zbMATH Keywords: threshold circuits
zbMATH Keywords: \(\text{MOD}_ m\) gates
MaRDI profile type: Publication
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Depth reduction for circuits of unbounded fan-in
cites work: Non-uniform automata over groups
cites work: Representing Boolean functions as polynomials modulo composite numbers
cites work: When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
cites work: On ACC
cites work: A note on a theorem of Barrington, Straubing and Thérien
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: A note on the power of majority gates and modular gates
cites work: An oracle separating \(\oplus P\) from \(PP^{PH}\)
cites work: A weight-size trade-off for circuits with MOD \(m\) gates
cites work: A guided tour of Chernoff bounds
cites work: Threshold circuits of bounded depth
cites work: On the power of small-depth threshold circuits
cites work: Some notes on threshold circuits, and multiplication in depth 4
cites work: On the computational power of depth-2 circuits with threshold and modulo gates
cites work: Threshold circuits of small majority-depth
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
cites work: Circuits constructed with MOD\(_ q\) gates cannot compute ``and'' in sublinear size
Recommended article: Top-down lower bounds for depth-three circuits
Recommended article: A lower bound for depth-3 circuits with MOD \(m\) gates
Recommended article: Exponential size lower bounds for some depth three circuits
Recommended article: Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates
Recommended article: Lower bounds for depth-three circuits with equals and mod-gates
Recommended article: Q5009530
Recommended article: Exponential lower bounds for depth three Boolean circuits
Recommended article: Multi-\(k\)-ic depth three circuit lower bound
Recommended article: Multi-k-ic Depth Three Circuit Lower Bound
Recommended article: Q4526973
description: scientific article; zbMATH DE number 1109555