Pith. sign in

REVIEW 6 minor 51 references

On the Computational Complexity of (Extended) Threshold Dimension and (Semi-)Ladder Index

T0 review · 0 major / 6 minor · reviewed 2026-07-31 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Computing extended threshold dimension is both NP-hard and co-NP-hard, with strong inapproximability under Gap-ETH.

desk verdict Clean NP/co-NP and Gap-ETH hardness package for Threshold/ExThD and ladder indices; the reductions check out and partially answer the SODA 2026 question. read the letter →

arxiv 2607.28355 v1 pith:WHIIRX7K submitted 2026-07-30 cs.CC

Pasin Manurangsi This is my paper
classification cs.CC MSC 68Q1768Q25
keywords thresholddimensionextendedladderindexsemi-ladderNP-hardnesshardnessofapproximationGap-ETHhypothesisclasses
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that deciding the threshold dimension of a finite hypothesis class is NP-complete, while the extended threshold dimension is both NP-hard and co-NP-hard. It further shows, assuming Gap-ETH, that neither dimension admits a polynomial-time n^o(1)-approximation or an FPT o(k)-approximation, and the same barriers hold for the ladder and semi-ladder indices of bipartite graphs. The results are obtained by reductions that route through a strengthened balanced-biclique promise problem and through ladder-index problems that already appear in parameterized-algorithm design. A reader who uses these dimensions to bound online learning with replays, or to design FPT algorithms, therefore faces genuine computational obstacles even for approximate computation. The work partially answers an open complexity question about extended threshold dimension.

What carries the argument

A chain of polynomial reductions from a strengthened Gap-Balanced-Biclique (YES: k-clique; NO: bipartite double cover has no large balanced biclique) through Gap-(Semi-)Ladder-Index and Gap-(Closure-)Threshold-Dimension into Gap-Extended-Threshold-Dimension, together with a direct co-NP-hardness reduction from Balanced 2-2-Set Splitting.

What would settle it

An FPT algorithm that distinguishes threshold dimension at least k from at most k/o(k), or a polynomial-time algorithm that correctly decides whether extended threshold dimension is at least a given k, would refute the central claims under the stated assumptions.

Watch

Extended reading notes

Core claim

Threshold-Dimension is NP-complete. Extended-Threshold-Dimension is both NP-hard and co-NP-hard. Under Gap-ETH there is no polynomial-time |X|^o(1)- or |H|^o(1)-approximation and no FPT o(k)-approximation for either dimension, and the same hardness holds for Ladder-Index and Semi-Ladder-Index.

Load-bearing premise

The approximation lower bounds stand only if Gap-ETH hardness for balanced biclique already holds in the special bipartite-double-cover form used by the reductions; if that source hardness fails, the approximation claims collapse while the exact NP and co-NP results remain.

Editorial extensions

If this is right

  • Exact computation of extended threshold dimension is unlikely to lie in NP or in co-NP alone.
  • Ladder and semi-ladder indices that appear in FPT algorithm design are themselves NP-hard and hard to approximate.
  • Any learning or privacy bound that requires computing (extended) threshold dimension inherits these computational barriers.
  • Finding a shift that realises the minimum extended threshold dimension is NP-hard.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The natural next target left open by the paper is Π₂-completeness of Extended-Threshold-Dimension.
  • The remaining gap between the trivial linear approximation and the n^o(1) hardness leaves open the possibility of intermediate polynomial approximations.
  • The same biclique-to-ladder reduction pattern may apply to other learning-theoretic dimensions that involve closures or shifts.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies the computational complexity of Threshold dimension (ThD) and Extended Threshold dimension (ExThD) of finite hypothesis classes, together with the related Ladder and Semi-Ladder indices of bipartite graphs. It proves that Threshold-Dimension is NP-complete (Theorem 1), that Extended-Threshold-Dimension is both NP-hard and co-NP-hard (Theorems 4–5), and that both Ladder-Index and Semi-Ladder-Index are NP-complete (Theorem 8). Under Gap-ETH it further establishes strong inapproximability: no polynomial-time |X|^o(1) or |H|^o(1) approximation and no FPT o(k)-approximation for either dimension, and the analogous n^o(1) and FPT o(k) lower bounds for the two indices (Theorems 2–3, 6–7, 9–10). The arguments proceed by a chain of explicit polynomial reductions (Maximum-Edge-Biclique / Gap-Balanced-Biclique o Gap-(Semi-)Ladder-Index o Gap-(Closure-)Threshold-Dimension o Gap-Extended-Threshold-Dimension) that rely on a clean generator characterization of ThD of the closure (Lemma 1) and on standard monotonicity observations for restrictions and twins. A separate reduction from Balanced 2-2-Set Splitting yields the co-NP-hardness of ExThD. An appendix also settles a related question on the existence of intersection-closed representations.

Significance. The results give the first systematic complexity-theoretic treatment of Threshold and Extended Threshold dimension, answering (in part) an open question of Dmitriev et al. (SODA 2026) and simultaneously supplying hardness for the Ladder/Semi-Ladder indices that have recently appeared in FPT algorithm design. The reductions are fully explicit, self-contained, and reuse a single structural lemma (Lemma 1) cleanly across several problems; the Gap-ETH inapproximability statements correctly inherit the precise B[G°]-form hardness of Manurangsi (STOC 2017) and Chalermsook et al. (SICOMP 2020). The co-NP-hardness of ExThD, together with the observation that an efficient argmin_f would collapse P and NP, is a particularly sharp contribution. These hardness results are of immediate interest to the computational-learning-theory and parameterized-algorithms communities.

minor comments (6)
  1. [Definition 1] Page 1 / Definition 1: the witness is written “t0,…,td ∈ H” while the surrounding text speaks of “thresholds au i”; a uniform notation would improve readability.
  2. [Lemma 1] Lemma 1 (⇒ direction): the extraction of gi from Ai-1 is correct but could be spelled out one sentence more carefully for readers unfamiliar with closures.
  3. [Theorem 11] Section 3.1, soundness of Theorem 11: the AM-GM step is clean, yet a short parenthetical remark that t = 2k^{2} is chosen precisely so that the final inequality is strict would help.
  4. [Section 5] Section 5, Case III of the co-NP soundness argument: the generators are listed correctly, but an explicit verification that gd+1 evaluates to 1 on all the chosen points would make the argument fully self-contained.
  5. A few typographical slips remain (e.g., “with replayswhere”, missing spaces after citations, “nendenotes”). A light copy-edit pass would remove them.
  6. [Appendix C] Appendix C is a nice bonus that answers another question of DFHS26; a one-sentence forward pointer in the introduction would make it more visible.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: standard self-contained many-one reductions from external NP-hard and Gap-ETH sources

full rationale

The paper proves NP-/co-NP-hardness and Gap-ETH inapproximability for Threshold dimension, Extended threshold dimension, Ladder index, and Semi-ladder index via explicit combinatorial reductions. Completeness and soundness are argued directly from definitions (generator characterization Lemma 1, twin/constant observations, AM-GM counting in ladder soundness, case analysis for ExThD co-NP reduction). Source problems are external: 3-SAT (Appendix B), Balanced 2-2-Set Splitting (Gur04), and published Gap-Balanced-Biclique hardness in the precise B[G°] form (Man17a, CCK+20). Author self-citations supply only black-box hardness assumptions already in the literature; they are not used to define the target quantities or to force the claimed dimensions by construction. No fitted parameter is renamed a prediction, no uniqueness theorem is imported to forbid alternatives, and no quantity is defined in terms of the result it purportedly derives. Score 0 is appropriate.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

Pure complexity-theoretic paper. Load-bearing external ingredients are standard NP-hardness of 3-SAT and 2-2-Set Splitting, plus Gap-ETH hardness of a strengthened Maximum Balanced Biclique promise problem from prior work. No fitted parameters; no new physical or mathematical entities beyond definitional promise problems used as intermediate vehicles.

assumptions (4)
  • domain assumption Gap-ETH: for some δ>0 there is no 2^{o(n)}-time algorithm distinguishing satisfiable 3CNF from (1-δ)-satisfiable 3CNF.
    Invoked for all approximation and FPT-approximation lower bounds (Theorems 2–3, 6–7, 9–10) via Theorems 12–13.
  • standard math 3-SAT is NP-complete; Balanced 2-2-Set Splitting is NP-hard (Gur04, with balancedness verified in Appendix A).
    Base of exact NP-hardness (Lemma 2 / Appendix B) and co-NP-hardness (Lemma 6 / Theorem 5).
  • domain assumption Published Gap-ETH hardness of Gap-Balanced-Biclique in the B[G°] form (Man17a, CCK+20).
    Theorems 12–13; paper states these can be verified to match the required promise form. Approximation chain (Lemma 5 onward) rests on them.
  • standard math P ≠ NP (and NP ≠ co-NP for the interpretive consequence that ExThD is unlikely in NP).
    Background for interpreting NP- and co-NP-hardness; Corollary 1 uses P ≠ NP explicitly.
invented entities (1)
  • Promise problems Gap-(Semi-)Ladder-Index, Gap-(Closure-)Threshold-Dimension, Gap-Extended-Threshold-Dimension, Maximum-Edge-Biclique, Gap-Balanced-Biclique
    purpose: Intermediate vehicles that let the reduction chain carry both exact and gap hardness cleanly.
    Definitional; not ontological posits. Standard technique in hardness-of-approximation papers.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Computational Complexity of (Extended) Threshold Dimension and (Semi-)Ladder Index." pith.science (2026). https://pith.science/paper/WHIIRX7K

@misc{pith2026260728355,
  author       = {Pith},
  title        = {Pith review of: On the Computational Complexity of (Extended) Threshold Dimension and (Semi-)Ladder Index},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WHIIRX7K}},
  note         = {Machine review of arXiv:2607.28355}
}
read the original 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.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

51 extracted references · 11 canonical work pages

  1. [1]

    STACS , pages =

    Grzegorz Fabianski and Michal Pilipczuk and Sebastian Siebertz and Szymon Torunczyk , title =. STACS , pages =. 2019 , url =. doi:10.4230/LIPICS.STACS.2019.27 , timestamp =

    doi:10.4230/lipics.stacs.2019.27 2019

  2. [2]

    Algorithmica , volume =

    Venkatesan Guruswami , title =. Algorithmica , volume =. 2004 , url =. doi:10.1007/S00453-003-1072-Z , timestamp =

    work page doi:10.1007/s00453-003-1072-z 2004

  3. [3]

    Tight Hardness Results for Minimizing Discrepancy , booktitle =

    Moses Charikar and Alantha Newman and Aleksandar Nikolov , editor =. Tight Hardness Results for Minimizing Discrepancy , booktitle =. 2011 , url =. doi:10.1137/1.9781611973082.124 , timestamp =

    work page doi:10.1137/1.9781611973082.124 2011

  4. [4]

    SODA , pages =

    Daniil Dmitriev and Harald Eskelund Franck and Carolin Heinzler and Amartya Sanyal , title =. SODA , pages =. 2026 , url =. doi:10.1137/1.9781611978971.239 , timestamp =

    work page doi:10.1137/1.9781611978971.239 2026

  5. [5]

    1978 , publisher=

    Classification theory and the number of non-isomorphic models , author=. 1978 , publisher=

    1978

  6. [6]

    1997 , publisher=

    A Shorter model theory , author=. 1997 , publisher=

    1997

  7. [7]

    STOC , pages =

    Alon, Noga and Livni, Roi and Malliaris, Maryanthe and Moran, Shay , title =. STOC , pages =. 2019 , isbn =

    2019

  8. [8]

    Littlestone, Nick , title =. Mach. Learn. , pages =. 1988 , publisher =

    1988

Show all 51 references
  1. [9]

    COLT , pages =

    Pasin Manurangsi and Aviad Rubinstein , title =. COLT , pages =. 2017 , url =

    2017

  2. [10]

    STOC , year =

    Feige, Uriel , title =. STOC , year =. doi:10.1145/509907.509985 , acmid =

  3. [11]

    A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem , journal =

    Noga Alon and L. A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem , journal =. 1986 , url =. doi:10.1016/0196-6774(86)90019-2 , timestamp =

    1986 doi

  4. [12]

    STACS , pages =

    Piotr Berman and Georg Schnitger , title =. STACS , pages =. 1989 , url =. doi:10.1007/BFb0028990 , timestamp =

    1989 doi

  5. [13]

    ITCS , pages =

    Pasin Manurangsi and Aviad Rubinstein and Tselil Schramm , title =. ITCS , pages =. 2021 , url =. doi:10.4230/LIPIcs.ITCS.2021.10 , timestamp =

    2021 doi

  6. [14]

    2020 , url =

    Parinya Chalermsook and Marek Cygan and Guy Kortsarz and Bundit Laekhanukit and Pasin Manurangsi and Danupon Nanongkai and Luca Trevisan , title =. 2020 , url =. doi:10.1137/18M1166869 , timestamp =

    2020 doi

  7. [15]

    Irit Dinur , title =. J. 2007 , url =. doi:10.1145/1236457.1236459 , timestamp =

    2007

  8. [16]

    STOC , pages =

    Pasin Manurangsi , title =. STOC , pages =. 2017 , url =. doi:10.1145/3055399.3055412 , timestamp =

    2017

  9. [17]

    A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms , journal =

    Andreas Emil Feldmann and. A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms , journal =. 2020 , url =. doi:10.3390/a13060146 , timestamp =

    2020 doi

  10. [18]

    Downey and Patricia A

    Rodney G. Downey and Patricia A. Evans and Michael R. Fellows , title =. COLT , pages =. 1993 , url =. doi:10.1145/168304.168311 , timestamp =

    1993

  11. [19]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows , title =. 2013 , url =. doi:10.1007/978-1-4471-5559-1 , isbn =

    2013 doi

  12. [20]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized Algorithms , publisher =. 2015 , url =. doi:10.1007/978-3-319-21275-3 , isbn =

    2015 doi

  13. [21]

    Cristina Bazgan and Florent Foucaud and Florian Sikora , title =. Theor. Comput. Sci. , volume =. 2019 , url =. doi:10.1016/j.tcs.2018.09.013 , timestamp =

    2019 doi

  14. [22]

    Marcus Schaefer , title =. J. Comput. Syst. Sci. , volume =. 1999 , url =. doi:10.1006/jcss.1998.1602 , timestamp =

    1999

  15. [23]

    CCC , pages =

    Marcus Schaefer , title =. CCC , pages =. 2000 , url =. doi:10.1109/CCC.2000.856750 , timestamp =

    2000

  16. [24]

    Elchanan Mossel and Christopher Umans , title =. J. Comput. Syst. Sci. , volume =. 2002 , url =. doi:10.1016/S0022-0000(02)00022-3 , timestamp =

    2002 doi

  17. [25]

    Papadimitriou and Mihalis Yannakakis , title =

    Christos H. Papadimitriou and Mihalis Yannakakis , title =. J. Comput. Syst. Sci. , volume =. 1996 , url =. doi:10.1006/jcss.1996.0058 , timestamp =

    1996

  18. [26]

    Moti Frances and Ami Litman , title =. Inf. Comput. , volume =. 1998 , url =. doi:10.1006/inco.1998.2709 , timestamp =

    1998

  19. [27]

    Russell Impagliazzo and Ramamohan Paturi and Francis Zane , title =. J. Comput. Syst. Sci. , volume =. 2001 , url =. doi:10.1006/jcss.2001.1774 , timestamp =

    2001

  20. [28]

    Russell Impagliazzo and Ramamohan Paturi , title =. J. Comput. Syst. Sci. , volume =. 2001 , url =. doi:10.1006/jcss.2000.1727 , timestamp =

    2001

  21. [29]

    The Parameterized Complexity of

    Bingkai Lin , editor =. The Parameterized Complexity of. SODA , pages =. 2015 , url =. doi:10.1137/1.9781611973730.41 , timestamp =

    2015 doi

  22. [30]

    Random Struct

    Mark Jerrum , title =. Random Struct. Algorithms , volume =. 1992 , url =. doi:10.1002/rsa.3240030402 , timestamp =

    1992 doi

  23. [31]

    Algorithms and Complexity: New Directions and Recent Results , year=

    Probabilistic analysis of some combinatorial search problems , author=. Algorithms and Complexity: New Directions and Recent Results , year=

  24. [32]

    ICALP , pages =

    Pasin Manurangsi and Prasad Raghavendra , title =. ICALP , pages =. 2017 , url =. doi:10.4230/LIPIcs.ICALP.2017.78 , timestamp =

    2017 doi

  25. [33]

    Electron

    Irit Dinur , title =. Electron. Colloquium Comput. Complex. , pages =. 2016 , url =

    2016

  26. [34]

    Clique is Hard to Approximate Within n^

    Johan H. Clique is Hard to Approximate Within n^. FOCS , pages =. 1996 , url =. doi:10.1109/SFCS.1996.548522 , timestamp =

    1996

  27. [35]

    Theory Comput

    David Zuckerman , title =. Theory Comput. , volume =. 2007 , url =. doi:10.4086/toc.2007.v003a006 , timestamp =

    2007 doi

  28. [36]

    ICALP , pages =

    Subhash Khot and Ashok Kumar Ponnuswami , title =. ICALP , pages =. 2006 , url =. doi:10.1007/11786986\_21 , timestamp =

    2006 doi

  29. [37]

    2006 , url =

    Subhash Khot , title =. 2006 , url =. doi:10.1137/S0097539705447037 , timestamp =

    2006 doi

  30. [38]

    ICALP , pages =

    Pasin Manurangsi , title =. ICALP , pages =. 2017 , url =. doi:10.4230/LIPIcs.ICALP.2017.79 , timestamp =

    2017 doi

  31. [39]

    2004 , institution =

    Hardness of Approximation of the Balanced Complete Bipartite Subgraph Problem , author =. 2004 , institution =

    2004

  32. [40]

    ICALP , pages =

    Amey Bhangale and Rajiv Gandhi and Mohammad Taghi Hajiaghayi and Rohit Khandekar and Guy Kortsarz , title =. ICALP , pages =. 2016 , url =. doi:10.4230/LIPIcs.ICALP.2016.6 , timestamp =

    2016 doi

  33. [41]

    Nick Littlestone , title =. Mach. Learn. , volume =. 1987 , url =. doi:10.1007/BF00116827 , timestamp =

    1987 doi

  34. [42]

    Vapnik, V. N. and Chervonenkis, A. Ya. , title =. Theory of Probability & Its Applications , volume =. 1971 , doi =

    1971

  35. [43]

    Steve Hanneke , title =. J. Mach. Learn. Res. , volume =. 2016 , url =

    2016

  36. [44]

    Warmuth , title =

    Anselm Blumer and Andrzej Ehrenfeucht and David Haussler and Manfred K. Warmuth , title =. J. 1989 , url =. doi:10.1145/76359.76371 , timestamp =

    1989

  37. [45]

    Theoretical Computer Science, Essays in Memory of Shimon Even , pages =

    Oded Goldreich , title =. Theoretical Computer Science, Essays in Memory of Shimon Even , pages =. 2006 , url =. doi:10.1007/11685654\_12 , timestamp =

    2006 doi

  38. [46]

    ITCS , pages =

    Pasin Manurangsi , title =. ITCS , pages =. 2023 , url =. doi:10.4230/LIPICS.ITCS.2023.85 , timestamp =

    2023 doi

  39. [47]

    The Parameterized Complexity of Computing the

    Foucaud, Florent and Gahlawat, Harmender and Mc Inerney, Fionn and Tale, Prafullkumar , booktitle =. The Parameterized Complexity of Computing the

  40. [48]

    STOC , pages =

    Prasad Raghavendra and David Steurer , title =. STOC , pages =. 2010 , url =. doi:10.1145/1806689.1806792 , timestamp =

    2010

  41. [49]

    CCC , pages =

    Subhash Khot , title =. CCC , pages =. 2002 , url =. doi:10.1109/CCC.2002.1004334 , timestamp =

    2002 arXiv

  42. [50]

    The maximum edge biclique problem is

    Ren. The maximum edge biclique problem is. Discret. Appl. Math. , volume =. 2003 , url =. doi:10.1016/S0166-218X(03)00333-0 , timestamp =

    2003 doi

  43. [51]

    2026 , month =

    Sanyal, Amartya , title =. 2026 , month =

    2026

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.