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

Abstract We prove that the complexity of computation of the threshold symmetric function <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msubsup> <m:mi>T</m:mi> <m:mi>n</m:mi> <m:mrow> <m:mi>n</m:mi> <m:mo>−</m:mo> <m:mn>1</m:mn> </m:mrow> </m:msubsup> </m:math> $T_n^{n-1}$ by monotone switching networks is Ω ( n log log n ).

Authors

Institutions

Publication Details

Journal
Discrete Mathematics and Applications
Published
2025-10-01
DOI
https://doi.org/10.1515/dma-2025-0026
Primary Topic
Complexity and Algorithms in Graphs
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

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

Igor S. Sergeev
Discrete Mathematics and Applications
Complexity and Algorithms in Graphs
article

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

Igor S. Sergeev
article en

Abstract

Abstract We prove that the complexity of computation of the threshold symmetric function <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msubsup> <m:mi>T</m:mi> <m:mi>n</m:mi> <m:mrow> <m:mi>n</m:mi> <m:mo>−</m:mo> <m:mn>1</m:mn> </m:mrow> </m:msubsup> </m:math> $T_n^{n-1}$ by monotone switching networks is Ω ( n log log n ).

Discrete Mathematics and ApplicationsVol. 35(5)
Research Institute "Quantum" (RU)
Openalex Percentile: Top 24%
Complexity and Algorithms in Graphs
DOISourceOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

A lower bound on the monotone switching complexity of the threshold function Tnn−1$T_n^{n-1}$ — Igor S. Sergeev · Discrete Mathematics and Applications (2025) | TGRS Research Map | TGRS