The bound on the number of sign vectors associated with an input

At least 3 years old · documented by

Let nn be a positive integer, let PxP_x be the region associated with a sign vector x∈{−1,+1}nx\in\{-1,+1\}^n, and let (C,c)(C,c) be a quadratic-programming input. The preceding proposition shows that an input may belong to multiple regions PxP_x. The region-count conjecture. For every input (C,c)(C,c), the membership relation (C,c)∈Px(C,c)\in P_x holds for at most nn distinct sign vectors x∈{−1,+1}nx\in\{-1,+1\}^n. This observation is based on computations reported in the source, which found at most nn such sign vectors; the supplied text does not establish the bound theoretically.

References

Primary source

Julia Lindberg and Jose Rodriguez, “Invariants of SDP exactness in quadratic programming”, arXiv:2211.05645 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.