Abstract:
We prove that the complexity of computation of the threshold symmetric function $T_n^{n-1}$ by monotone switching networks is $\Omega(n \log \log n)$.
\Bibitem{Ser23}
\by I.~S.~Sergeev
\paper A lower bound on the monotone switching complexity of the threshold function $T_n^{n-1}$
\jour Diskr. Mat.
\yr 2023
\vol 35
\issue 4
\pages 126--131
\mathnet{http://mi.mathnet.ru/dm1789}
\crossref{https://doi.org/10.4213/dm1789}