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

From papers

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.