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

A long-investigated problem in circuit complexity theory is to decompose an n-input or n-variable Majority Boolean function (call it Mₙ) using k-input ones (Mₖ), k < n, where the objective is to achieve the decomposition using fewest Mₖ's. An O (n) decomposition for Mₙ has been proposed recently with k=3. However, for an arbitrary value of k, no such construction exists even though there are several works reporting continual improvement of lower bounds, finally achieving an optimal lower bound (nk k) as provided by Lecomte et. al. , in CCC '22. In this direction, here we propose two decomposition procedures for Mₙ, utilizing counter trees and restricted partition functions, respectively. The construction technique based on counter tree requires O (n) such many Mₖ functions, hence presenting a construction closest to the optimal lower bound, reported so far. The decomposition technique using restricted partition functions present a novel link between Majority Boolean function construction and elementary number theory. These decomposition techniques close a gap in circuit complexity studies and are also useful for leveraging emerging computing technologies.