The relaxation complexity of the standard simplex is logarithmic
Not on the map. Why?
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).
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). First posted on arXiv 10 Jun 2026.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2026: 1.
1 paper.
- 2026Transformer Heads Looking for Ordercited by 0
- 2026Transformer Heads Looking for Order22 Sep 2026