# Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique

arXiv: https://arxiv.org/abs/2211.01443 · HTML: https://mlsanity.com/paper/2211.01443/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 43 references that are in the map.
- First posted on arXiv 2 Nov 2022.

## Builds on (most cited first, 3 of 3)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms](https://mlsanity.com/paper/2006.04411/) (2020)
- [The Strongish Planted Clique Hypothesis and Its Consequences](https://mlsanity.com/paper/2011.05555/) (2020)

## Built on by (most cited first, 7 of 7)

- [Online Learning and Solving Infinite Games with an ERM Oracle](https://mlsanity.com/paper/2307.01689/) (2023)
- [Simple online learning with consistent oracle](https://mlsanity.com/paper/2308.08055/) (2023)
- [Private PAC Learning May be Harder than Online Learning](https://mlsanity.com/paper/2402.11119/) (2024)
- [Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning](https://mlsanity.com/paper/2506.00135/) (2025)
- [The Parameterized Complexity of Computing the VC-Dimension](https://mlsanity.com/paper/2510.17451/) (2025)
- [Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning](https://mlsanity.com/paper/2605.07155/) (2026)
- [A Note on Hardness of Computing Recursive Teaching Dimension](https://mlsanity.com/paper/2307.09792/) (2023)

## Abstract (arXiv)

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 [Manurangsi and Rubinstein, COLT 2017].