Linear Decomposition of the Majority Boolean Function using the Ones on Smaller Variables

Anupam Chattopadhyay, Debjyoti Bhattacharjee, Subhamoy Maitra

A long-investigated problem in circuit complexity theory is to decompose an $n$-input or $n$-variable Majority Boolean function (call it $M_n$) using $k$-input ones ($M_k$), $k < n…