A Polynomial Bound on Split Rank
We prove that the split rank of a rational pure-integer polyhedron is polynomially bounded in its input length, resolving a conjecture of Basu, Conforti, Di Summa, and Jiang. If the defining system has dense binary encoding length $L$, then $O((L+1)^9)$ split rounds suffice to reach the integer hull in arbitrary dimension.
Authors
- Avinash Bhardwaj (ORCID: https://orcid.org/0000-0002-9690-1705)
- Vishnu Narayanan (ORCID: https://orcid.org/0009-0009-0180-6675)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.48550/arxiv.2611.16231
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint