On Expressing Majority as a Majority of Majorities

DOI10.1137/18M1223599zbMath1460.94091MaRDI QIDQ5220471

No author found.

Publication date: 26 March 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

lower boundmajorityBoolean circuits

Mathematics Subject Classification ID

Analytic circuit theory (94C05)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Lower bounds and separations for constant depth multilinear circuits
• Boolean function complexity. Advances and frontiers.
• Sorting in \(c \log n\) parallel steps
• ``Integer-making theorems
• Short monotone formulae for the majority function
• On the Distribution of the Number of Successes in Independent Trials
• Amplifying lower bounds by means of self-reducibility
• Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates
• Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

This page was built for publication: On Expressing Majority as a Majority of Majorities