Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
- 29 November 2018
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 63 (5) , 956-986
Abstract
No abstract availableKeywords
All Related Versions
Funding Information
- Russian Science Foundation (16-11-10123)
- MK (MK-5379.2018.1)
- Russian Academic Excellence Project ’5-100’
This publication has 14 references indexed in Scilit:
- Improved bounds for the randomized decision tree Complexity of recursive majorityRandom Structures & Algorithms, 2015
- Analysis of Boolean Functions2014
- Amplifying lower bounds by means of self-reducibilityJournal of the ACM, 2010
- Concentration of Measure for the Analysis of Randomized Algorithms2009
- Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient CryptographySIAM Journal on Computing, 2007
- On the noise sensitivity of monotone functionsRandom Structures & Algorithms, 2003
- Majority gates vs. general weighted threshold gatescomputational complexity, 1992
- On the Power of Threshold Circuits with Small WeightsSIAM Journal on Discrete Mathematics, 1991
- Short monotone formulae for the majority functionJournal of Algorithms, 1984
- Probability Inequalities for the Sum in Sampling without ReplacementThe Annals of Statistics, 1974