Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

DOI10.4230/LIPICS.STACS.2017.49zbMath1402.68100arXiv1610.02686OpenAlexW2531652110MaRDI QIDQ4636650

Vladimir V. Podolskii, Alexander S. Kulikov

Publication date: 19 April 2018

Full work available at URL: https://arxiv.org/abs/1610.02686

zbMATH Keywords

computational complexityupper boundlower boundcircuit complexitythresholdmajority

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (4)

Unnamed Item ⋮ A circuit of depth two with limited input branching for majority functions ⋮ On Expressing Majority as a Majority of Majorities ⋮ 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