Computing majority by constant depth majority circuits with low fan-in gates
DOI10.1007/S00224-018-9900-3zbMATH Open1429.68082OpenAlexW3023847609WikidataQ128899656 ScholiaQ128899656MaRDI QIDQ2321926FDOQ2321926
Vladimir V. Podolskii, Alexander S. Kulikov
Publication date: 27 August 2019
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/6983/
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Analysis of Boolean Functions
- Title not available (Why is that?)
- Boolean function complexity. Advances and frontiers.
- Majority gates vs. general weighted threshold gates
- Concentration of Measure for the Analysis of Randomized Algorithms
- Concentration of the hypergeometric distribution
- Short monotone formulae for the majority function
- Extremal Combinatorics
- Probability inequalities for the sum in sampling without replacement
- Amplifying lower bounds by means of self-reducibility
- On the Power of Threshold Circuits with Small Weights
- On the noise sensitivity of monotone functions
- Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- On (Valiant’s) Polynomial-Size Monotone Formula for Majority
- Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- Improved bounds for the randomized decision tree complexity of recursive majority
Cited In (1)
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)
