Skip to content
DraconiticResearch
Search Sources API
178,970 studies31 sourcesUpdated 14 min ago
PreprintarXiv licencearXiv

Computing Lower Bounds on the Non-negative Rank via SAT Solvers

  • Tilman Engel
  • Thomas Kalinowski
  • Matthias Schymura
Open at sourcePDFDOICite

Abstract

Finding the extension complexity (xc) of a polytope is equivalent to finding the non-negative rank of its slack matrix. We provide a formulation for the rectangle and refined rectangle covering, bounding the non-negative rank of diverse non-negative matrices. While the bounds are known, our formulation enables us to use boolean satisfiability (SAT) solvers, which proves to be a strong tool. We obtain improved values for lower bounds on the non-negative rank of multiple matrices. In particular, we determined the xc of some regular polygons.

Related

  1. Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers
    Timothy Baeckelant, Arnaud Vandaele, Nicolas Gillis
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Border rank lower bounds beyond weak border apolarity
    Tomasz Mańdziuk
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  3. Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
    Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana +4
    arXivPreprintarXiv licenceFull textOptimisation & controlQuantum physics & quantum informationarXiv
  4. Low-cost non-iterative Sylvester solvers for dynamical low-rank approximation of reaction-diffusion equations
    Joy Saha, Jun Yang, Peimeng Yin
    arXivPreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv
  5. Computing Smooth Geodesics under Two-Sided Curvature Bounds with Applications to Robotics and Image Analysis
    Da Chen, Zhenjiang Li, Jean-Marie Mirebeau +4
    HALPreprintLicence not statedNumerical analysis & scientific computingHAL

Cite

BibTeXRIS
BibTeX
@misc{engel2026computing,
  title = {{Computing Lower Bounds on the Non-negative Rank via SAT Solvers}},
  author = {Tilman Engel and Thomas Kalinowski and Matthias Schymura},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.11950},
  eprint = {2610.11950},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.11950},
}
RIS
TY  - UNPB
TI  - Computing Lower Bounds on the Non-negative Rank via SAT Solvers
AU  - Tilman Engel
AU  - Thomas Kalinowski
AU  - Matthias Schymura
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.11950
UR  - https://arxiv.org/abs/2610.11950
AB  - Finding the extension complexity (xc) of a polytope is equivalent to finding the non-negative rank of its slack matrix. We provide a formulation for the rectangle and refined rectangle covering, bounding the non-negative rank of diverse non-negative matrices. While the bounds are known, our formulation enables us to use boolean satisfiability (SAT) solvers, which proves to be a strong tool. We obtain improved values for lower bounds on the non-negative rank of multiple matrices. In particular, we determined the xc of some regular polygons.
ER  -