On the power of small-depth threshold circuits

DOI10.1007/BF01272517zbMath0774.68060OpenAlexW2107998050WikidataQ56959173 ScholiaQ56959173MaRDI QIDQ685717

Publication date: 10 October 1993

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01272517

zbMATH Keywords

monotone circuits lower bounds circuit complexity threshold circuits

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

Related Items (56)

Sharp Bounds for the Number of Regions of Maxout Networks and Vertices of Minkowski Sums ⋮ On relations between counting communication complexity classes ⋮ $n^{{\Omega{}}(\log{} n)}$ lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom ⋮ The correlation between parity and quadratic polynomials mod $3$ ⋮ On the power of a threshold gate at the top ⋮ Hellinger volume and number-on-the-forehead communication complexity ⋮ Local Reductions ⋮ On small depth threshold circuits ⋮ Interactive Information Complexity ⋮ Local reduction ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Interactive Information Complexity ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ Hadamard tensors and lower bounds on multiparty communication complexity ⋮ The function-inversion problem: barriers and opportunities ⋮ A lower bound for monotone perceptrons ⋮ Decomposition of threshold functions into bounded fan-in threshold functions ⋮ Neural networks and complexity theory ⋮ On the power of circuits with gates of low $L_{1}$ norms. ⋮ Energy and fan-in of logic circuits computing symmetric Boolean functions ⋮ DECISION TREES DO NOT GENERALIZE TO NEW VARIATIONS ⋮ Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols ⋮ Globally Convergent Multilevel Training of Deep Residual Networks ⋮ Unnamed Item ⋮ Depth-efficient threshold circuits for multiplication and symmetric function computation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Non-deterministic Communication Complexity of Regular Languages ⋮ Unexpected upper bounds on the complexity of some communication games ⋮ The NOF multiparty communication complexity of composed functions ⋮ A note on the power of majority gates and modular gates ⋮ Energy and Fan-In of Threshold Circuits Computing Mod Functions ⋮ Size, Depth and Energy of Threshold Circuits Computing Parity Function. ⋮ Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity ⋮ The communication complexity of addition ⋮ Harmonic analysis, real approximation, and the communication complexity of Boolean functions ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ On the correlation between parity and modular polynomials ⋮ Noise sensitivity of Boolean functions and applications to percolation ⋮ Deep Belief Networks Are Compact Universal Approximators ⋮ ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ Quantum multiparty communication complexity and circuit lower bounds ⋮ A note on multiparty communication complexity and the Hales-Jewett theorem ⋮ On the relationship between energy complexity and other Boolean function measures ⋮ On Functions Computed on Trees ⋮ The Multiparty Communication Complexity of Set Disjointness ⋮ Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates ⋮ Unnamed Item ⋮ A lower bound for perceptrons and an oracle separation of the $PP^{PH}$ hierarchy ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Unnamed Item ⋮ Communication Lower Bounds Using Directional Derivatives

Cites Work

This page was built for publication: On the power of small-depth threshold circuits