Threshold circuits of small majority-depth
From MaRDI portal
Publication:1273878
DOI10.1006/inco.1998.2732zbMath0916.68060OpenAlexW2107145684MaRDI QIDQ1273878
Publication date: 6 January 1999
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/5dcbb6ce94a860df0c061c3ea4fe8465f2bd6c8e
Related Items (12)
Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in \({\mathsf {TC}^0}\) ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ Decomposition of threshold functions into bounded fan-in threshold functions ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ Algebraic algorithms for variants of subset sum ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Parity helps to compute majority ⋮ The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\) ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Efficient threshold circuits for power series ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Bounded-depth, polynomial-size circuits for symmetric functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Some notes on threshold circuits, and multiplication in depth 4
- Majority gates vs. general weighted threshold gates
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- On ACC
- The complexity of iterated multiplication
- Threshold circuits of bounded depth
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- Harmonic Analysis of Polynomial Threshold Functions
- Log Depth Circuits for Division and Related Problems
- Definability by constant-depth polynomial-size circuits
- On the Power of Threshold Circuits with Small Weights
- Depth efficient neural networks for division and related problems
- Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition
- On Optimal Depth Threshold Circuits for Multiplication and Related Problems
- Simulating threshold circuits by majority circuits
- Depth-size tradeoffs for neural computation
This page was built for publication: Threshold circuits of small majority-depth
