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
Fulltext:
PDF file (504 kB)
References
©
Steklov Math. Inst. of RAS
, 2025