mlsanityData to 14 Oct 2026

The relaxation complexity of the standard simplex is logarithmic

arXiv 2606.11852 ↗First posted 10 Jun 2026cs.DM math.CO math.OCcited by 1

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

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.