2026-07-22T06:25:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17588 2024-03-06T10:59:59Z ddc:004 open_access

Improved Inapproximability of VC Dimension and Littlestone’s Dimension via (Unbalanced) Biclique Manurangsi, Pasin VC Dimension Littlestone’s Dimension Maximum Biclique Hardness of Approximation Fine-Grained Complexity We study the complexity of computing (and approximating) VC Dimension and Littlestone’s Dimension when we are given the concept class explicitly. We give a simple reduction from Maximum (Unbalanced) Biclique problem to approximating VC Dimension and Littlestone’s Dimension. With this connection, we derive a range of hardness of approximation results and running time lower bounds. For example, under the (randomized) Gap-Exponential Time Hypothesis or the Strongish Planted Clique Hypothesis, we show a tight inapproximability result: both dimensions are hard to approximate to within a factor of o(log n) in polynomial-time. These improve upon constant-factor inapproximability results from [Pasin Manurangsi and Aviad Rubinstein, 2017]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pasin Manurangsi 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.85 urn:nbn:de:0030-drops-175884 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.85 eng https://creativecommons.org/licenses/by/4.0/legalcode