Computing majority by constant depth majority circuits with low fan-in gates
From MaRDI portal
Publication:2321926
Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)
Recommendations
- Computing majority by constant depth majority circuits with low fan-in gates
- Threshold circuits of small majority-depth
- Bounds on the Size of Small Depth Circuits for Approximating Majority
- A circuit of depth two with limited input branching for majority functions
- On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
- Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition
- On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
- Using amplification to compute majority with small majority gates
- scientific article; zbMATH DE number 549850
- Publication:4728251
Cites work
- scientific article; zbMATH DE number 815575 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- scientific article; zbMATH DE number 3314813 (Why is no real title available?)
- Amplifying lower bounds by means of self-reducibility
- Analysis of Boolean Functions
- Boolean function complexity. Advances and frontiers.
- Computing majority by constant depth majority circuits with low fan-in gates
- Concentration of Measure for the Analysis of Randomized Algorithms
- Concentration of the hypergeometric distribution
- Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
- Extremal combinatorics. With applications in computer science
- Improved bounds for the randomized decision tree complexity of recursive majority
- Majority gates vs. general weighted threshold gates
- On (Valiant’s) Polynomial-Size Monotone Formula for Majority
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- On the Power of Threshold Circuits with Small Weights
- On the noise sensitivity of monotone functions
- Probability inequalities for the sum in sampling without replacement
- Short monotone formulae for the majority function
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
Cited in
(6)- On expressing majority as a majority of majorities
- Majority is incompressible by \(\mathrm{AC}^0[p]\) circuits
- A circuit of depth two with limited input branching for majority functions
- Depth two majority circuits for majority and list expanders
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- Computing majority by constant depth majority circuits with low fan-in gates
This page was built for publication: Computing majority by constant depth majority circuits with low fan-in gates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2321926)
