Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity
From MaRDI portal
Publication:955021
DOI10.1016/j.tcs.2008.07.028zbMath1152.68047OpenAlexW1979569157MaRDI QIDQ955021
Publication date: 18 November 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.07.028
Learning and adaptive systems in artificial intelligence (68T05) Neural networks for/in biological studies, artificial life and related topics (92B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Size and Energy of Threshold Circuits Computing Mod Functions ⋮ Energy and fan-in of logic circuits computing symmetric Boolean functions ⋮ Energy and depth of threshold circuits ⋮ Size-energy tradeoffs for unate circuits computing symmetric Boolean functions ⋮ Energy Complexity of Recurrent Neural Networks ⋮ Energy and Fan-In of Threshold Circuits Computing Mod Functions ⋮ Size, Depth and Energy of Threshold Circuits Computing Parity Function. ⋮ New bounds for energy complexity of Boolean functions ⋮ On the relationship between energy complexity and other Boolean function measures ⋮ ENERGY-EFFICIENT THRESHOLD CIRCUITS COMPUTING MOD FUNCTIONS
Cites Work
- On the power of small-depth threshold circuits
- A linear lower bound on the unbounded error probabilistic communication complexity.
- \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom
- Threshold circuits of bounded depth
- On the Computational Power of Threshold Circuits with Sparse Activity
- Upper and lower bounds on switching energy in VLSI
- Communication Complexity
- Mathematical Foundations of Computer Science 2005
- How Close Are We to Understanding V1?
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item