Realization of linear functions by formulas in various bases (Q1866895)

The author studies the complexity of the realization of a linear Boolean function \(x_1\oplus\dots\oplus x_n\) by formulas in various bases. The author divides all the bases into three types: in the bases of the first type, the order of the complexity of realization of a linear function equals \(n^2\); in the bases of the second type, the order of complexity is not smaller than \(n^\beta\) and not larger than \(n^\gamma\), where \(1<\beta<\gamma<2\) (the constants \(\beta\) and \(\gamma\) are calculated with respect to the basis); and in the bases of the third type, the order of complexity equals \(n\).