Research and Construction of Monotonous Circuits of Small Depth Computing Symmetric Threshold Function

In this work, a study was conducted on the computability of the MAJ[n] voting function and the approximate AppMAJ[n,ε] voting function by monotone circuits of small depth, and several new estimations for the depth of such circuits were also proved. The aim was to generalize the existing results concerning Boolean circuits for MAJ[n]/AppMAJ[n,ε]. To do this, an attempt was made to derive and prove new upper and lower bounds to the depth, which would depend on the non-constant parameters n and ε. As the result, a new upper bound O(1 + log(1/ε)/log(log(n))) was obtained for the minimum depth of the unbound fan-in circuit of polynomial size calculating AppMAJ[n,ε]. In particular cases, this estimate also improves the existing results: on the one hand, we have the bound of Θ(log(n)/log(log(n))) for the usual MAJ[n] (that is, an upper estimate was obtained that coincided with the previously known lower one); on the other hand, we also have a constant depth estimate for AppMAJ[n,ε], ε=1/poly(log(n)).