Computing majority by constant depth majority circuits with low fan-in gates
DOI10.1007/s00224-018-9900-3zbMath1429.68082OpenAlexW3023847609WikidataQ128899656 ScholiaQ128899656MaRDI QIDQ2321926
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/
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Networks and circuits as models of computation; circuit complexity (68Q06)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boolean function complexity. Advances and frontiers.
- Majority gates vs. general weighted threshold gates
- On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs
- Probability inequalities for the sum in sampling without replacement
- Concentration of the hypergeometric distribution
- Improved bounds for the randomized decision tree Complexity of recursive majority
- Extremal Combinatorics
- Short monotone formulae for the majority function
- Amplifying lower bounds by means of self-reducibility
- On the Power of Threshold Circuits with Small Weights
- On the noise sensitivity of monotone functions
- Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
- On (Valiant’s) Polynomial-Size Monotone Formula for Majority
- Analysis of Boolean Functions
- Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits
- Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
- Concentration of Measure for the Analysis of Randomized Algorithms
This page was built for publication: Computing majority by constant depth majority circuits with low fan-in gates
