Computing majority by constant depth majority circuits with low fan-in gates
type: Item
instance of: scholarly article
title: Computing majority by constant depth majority circuits with low fan-in gates
zbMATH Open document ID: 1429.68082
author: Alexander S. Kulikov
author: Vladimir V. Podolskii
published in: Theory of Computing Systems
publication date: 2019-08-27T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/6983/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q06
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 94C11
zbMATH DE Number: 7098515
zbMATH Keywords: circuit complexity
zbMATH Keywords: constant depth
zbMATH Keywords: majority
zbMATH Keywords: threshold
zbMATH Keywords: correlation
zbMATH Keywords: average case
zbMATH Keywords: worst case
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W3023847609
cites work: Amplifying lower bounds by means of self-reducibility
cites work: Concentration of Measure for the Analysis of Randomized Algorithms
cites work: Q5538132
cites work: Majority gates vs. general weighted threshold gates
cites work: On (Valiant’s) Polynomial-Size Monotone Formula for Majority
cites work: Concentration of the hypergeometric distribution
cites work: Extremal Combinatorics
cites work: Boolean function complexity. Advances and frontiers.
cites work: On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
cites work: Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
cites work: Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
cites work: Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
cites work: Improved bounds for the randomized decision tree complexity of recursive majority
cites work: Q5595902
cites work: On the noise sensitivity of monotone functions
cites work: Analysis of Boolean Functions
cites work: Q4855565
cites work: Probability inequalities for the sum in sampling without replacement
cites work: On the Power of Threshold Circuits with Small Weights
cites work: Short monotone formulae for the majority function
Wikidata QID: Q128899656
DOI: 10.1007/S00224-018-9900-3
Recommended article: Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
Recommended article: Threshold circuits of small majority-depth
Recommended article: Bounds on the Size of Small Depth Circuits for Approximating Majority
Recommended article: A circuit of depth two with limited input branching for majority functions
Recommended article: On the complexity of bounded-depth circuits and formulas over the basis of fan-in gates
Recommended article: Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition
Recommended article: On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
Recommended article: Using amplification to compute majority with small majority gates
Recommended article: Q4287354
Recommended article: Q4728251
description: scientific article; zbMATH DE number 7098515