RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2023 Volume 35, Issue 4, Pages 126–131 (Mi dm1789)

A lower bound on the monotone switching complexity of the threshold function $T_n^{n-1}$

I. S. Sergeev

Research Institute «Kvant», Moscow

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)$.

Keywords: switching networks, threshold functions, monotone computations.

UDC: 519.714.4

Received: 20.08.2023

DOI: 10.4213/dm1789



© Steklov Math. Inst. of RAS, 2025