Geodesic
A lower bound on the monotone switching complexity of the threshold function $T_n^{n-1}$
Diskretnaya Matematika, Tome 35 (2023) no. 4, pp. 126-131.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2023_35_4_a7,
     author = {I. S. Sergeev},
     title = {A lower bound on the monotone switching complexity of the threshold function $T_n^{n-1}$},
     journal = {Diskretnaya Matematika},
     pages = {126--131},
     publisher = {mathdoc},
     volume = {35},
     number = {4},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2023_35_4_a7/}
}
TY  - JOUR
AU  - I. S. Sergeev
TI  - A lower bound on the monotone switching complexity of the threshold function $T_n^{n-1}$
JO  - Diskretnaya Matematika
PY  - 2023
SP  - 126
EP  - 131
VL  - 35
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2023_35_4_a7/
LA  - ru
ID  - DM_2023_35_4_a7
ER  - 
%0 Journal Article
%A I. S. Sergeev
%T A lower bound on the monotone switching complexity of the threshold function $T_n^{n-1}$
%J Diskretnaya Matematika
%D 2023
%P 126-131
%V 35
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2023_35_4_a7/
%G ru
%F DM_2023_35_4_a7
I. S. Sergeev. A lower bound on the monotone switching complexity of the threshold function $T_n^{n-1}$. Diskretnaya Matematika, Tome 35 (2023) no. 4, pp. 126-131. http://geodesic.mathdoc.fr/item/DM_2023_35_4_a7/

[1] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984, 138 pp.

[2] Grinchuk M. I., O slozhnosti realizatsii simmetricheskikh bulevykh funktsii kontaktnymi skhemami, Diss. ... kand. fiz.-mat. nauk, M., 1989

[3] Grinchuk M. I., “Nizhnyaya otsenka slozhnosti realizatsii simmetricheskikh bulevykh funktsii kontaktnymi skhemami”, Matematicheskie voprosy kibernetiki, 4, Nauka, M., 1992, 130–138 | MR

[4] Razborov A. A., “Nizhnie otsenki slozhnosti realizatsii simmetricheskikh bulevykh funktsii kontaktno-ventilnymi skhemami”, Matematicheskie zametki, 48:6 (1990), 79–90

[5] Babai L., Pudlák P., Rödl V., Szemeredi E., “Lower bounds to the complexity of symmetric Boolean functions”, Theor. Comput. Sci., 74:3 (1990), 313–323 | DOI | MR | Zbl

[6] Markov A. A., “O minimalnykh kontaktno-ventilnykh dvukhpolyusnikakh dlya monotonnykh simmetricheskikh funktsii”, Problemy kibernetiki, 8, Fizmatlit, M., 1962, 117–121

[7] Krichevskii R. E., “Minimalnaya skhema iz zamykayuschikh kontaktov dlya odnoi bulevoi funktsii ot $n$ argumentov”, Diskretnyi analiz, 5, In-t matem. SO AN SSSR, Novosibirsk, 1965, 89–92

[8] Hansel G., “Nombre des lettres nécessaires pour écrire une fonction symétrique de $n$ variables”, C. R. Acad. Sci. Paris, 261:21 (1965), 1297–1300 | MR

[9] Krichevskii R. E., “Slozhnost kontaktnykh skhem, realizuyuschikh odnu funktsiyu algebry logiki”, Doklady AN SSSR, 151:4 (1963), 803–806 | Zbl

[10] Hansel G., “Nombre minimal de contacts de fermeture nécessaires pour réaliser une fonction booléenne symétrique de $n$ variables”, C. R. Acad. Sci. Paris, 258:25 (1964), 6037–6040 | MR | Zbl

[11] Radhakrishnan J., “Better lower bounds for monotone threshold formulas”, J. Computer and System Sciences, 54:2 (1997), 221–226 | DOI | MR | Zbl

[12] Halldórsson M. M., Radhakrishnan J., Subrahmanyam K. V., “Directed vs. undirected monotone contact networks for threshold functions”, Proc. $34$th FOCS (Palo Alto, USA), IEEE, 1993, 604–613 | MR