# The relaxation complexity of the standard simplex is logarithmic

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2026.

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

- [Transformer Heads Looking for Order](https://mlsanity.com/paper/2609.25588/) (2026)

## Abstract (arXiv)

For a set X of integer points, the relaxation complexity operatornamerc(X) is the smallest number of facets of any polyhedron P such that P cap mathbbZd = X. In this paper, we focus on the case where X is the discrete standard simplex Deltad = 0, e1, dots, ed. We show that operatornamerc(Deltad) = O(log d) by an explicit, elementary construction. This improves upon the previously best-known upper bound operatornamerc(Deltad) = O(d / √log d) due to Aprile, Averkov, Di Summa, and Hojny (2024) and matches an asymptotic lower bound by Averkov and Schymura (2022).