On the Computational Complexity of (Extended) Threshold Dimension and (Semi-)Ladder Index
arXiv:2607.28355
The paper investigates the difficulty of computing the threshold dimension and extended threshold dimension of hypothesis classes, proving NP‑hardness, co‑NP‑hardness, and strong hardness of approximation (including parameterized hardness), and also establishes similar hardness results for the ladder and semi‑ladder indices.
Abstract
We study the complexity of computing the Threshold dimension of a hypothesis class and its variant, the Extended threshold dimension. For the latter, we prove that it is both NP-hard and co-NP-hard, which (partially) answers an open question of Dmitriev et al. (SODA 2026). Furthermore, by relating the problem to a variant of Maximum Balanced Biclique, we prove strong hardness of approximation for both dimensions, including in the parameterized setting. As an intermediate result, we also prove hardness (of approximation) results for computing the ladder index and the semi-ladder index (Fabianski et al., STACS 2019), which have recently been used in the design of fixed-parameter tractable algorithms.