Metadata only
Date
2023Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
The Empty Integral Hull problem is a feasibility problem that is a linear representation of a subset of the Boolean Hypercube with n vertices with no integral points. In this paper, we study the Sum of Squares rank of the problem. We present a novel approach to derive SoS bounds by transforming the problem into a sequence of questions in the Boolean Function Analysis, positive definiteness of tri-diagonal matrices, and finally, into a problem from the field of Continued Fractions. The results showed for these intermediate problems are of independent interest. We apply the techniques to prove that the SoS rank for the Empty Integral Hull problem is at least n/2 + Omega(root n) Show more
Publication status
publishedExternal links
Book title
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic ComputationPages / Article No.
Publisher
Association for Computing MachineryEvent
Subject
combinatorial optimization; sum-of-squares; boolean analysis; boolean analysis; continued fractionsMore
Show all metadata
ETH Bibliography
yes
Altmetrics