# The VC-dimension of k-vertex d-polytopes

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2020.

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

- [Strategic Classification with Non-Linear Classifiers](https://mlsanity.com/paper/2505.23443/) (2025)
- [On Margin-Based Cluster Recovery with Oracle Queries](https://mlsanity.com/paper/2106.04913/) (2021)
- [Scalable Utility-Aware Multiclass Calibration](https://mlsanity.com/paper/2510.25458/) (2025)
- [How to Learn a Star: Binary Classification with Starshaped Polyhedral Sets](https://mlsanity.com/paper/2505.01346/) (2025)

## Abstract (arXiv)

In this short note, we show that the VC-dimension of the class of k-vertex polytopes in mathbb Rd is at most 8d2klog2k, answering an old question of Long and Warmuth.