arxiv: 2605.02896 · v1 · submitted 2026-03-20 · 🧮 math.OC · cs.CC

Recognition: no theorem link

Hardness of some optimization problems over correlation polyhedra

Alberto Caprara , Fabio Furini , Claudio Gentile , Leo Liberti , Andrea Lodi

Authors on Pith no claims yet

Pith reviewed 2026-05-15 08:46 UTC · model grok-4.3

classification 🧮 math.OC cs.CC

keywords NP-hardnesscorrelation polytopematrix coneKarp reductionrank decompositionrelaxed rankcombinatorial optimizationbinary matrices

0 comments

The pith

Membership, rank, and relaxed-rank problems over the correlation cone are NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes through explicit Karp reductions that three natural decision and optimization problems over the correlation cone are NP-hard: deciding whether a given matrix lies in the cone, computing the minimum number of rank-one 0-1 matrices whose sum equals the input, and computing the same quantity after replacing the counting norm with an L1 relaxation. These problems arise directly from the cone spanned by all n by n rank-one matrices with entries in {0,1}, which encodes pairwise correlations among binary variables. A reader cares because the same cone appears in combinatorial optimization, statistical modeling of binary data, and signal-processing tasks; proving that no polynomial-time algorithm exists for the exact versions therefore rules out efficient exact solvers unless P equals NP.

Core claim

We prove the NP-hardness, using Karp reductions, of the membership, rank of the decomposition, and relaxed rank problems for the correlation polytope and its corresponding cone spanned by all n by n rank-one matrices over {0,1}.

What carries the argument

The correlation cone, the set of all nonnegative linear combinations of n by n rank-one matrices whose entries lie in {0,1}.

If this is right

No polynomial-time algorithm exists for deciding membership in the correlation cone unless P equals NP.
Computing the exact number of rank-one 0-1 matrices needed to sum to a given matrix is NP-hard.
The L1-relaxed rank problem, used in signal-processing and statistical applications, is likewise NP-hard.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Practical work on binary correlation models will therefore need approximation algorithms or heuristics rather than exact solvers.
Related matrix cones arising in other combinatorial settings may inherit comparable hardness results through similar reductions.
Fixed-parameter algorithms or polynomial-time methods for restricted families (low dimension, sparsity, or additional symmetry) remain possible despite general hardness.

Load-bearing premise

The Karp reductions from known NP-hard problems to membership, rank, and relaxed-rank queries on the correlation cone are constructed correctly and do not introduce polynomially solvable special cases.

What would settle it

A polynomial-time algorithm that solves the membership problem for arbitrary matrices in the correlation cone would falsify the NP-hardness claim.

read the original abstract

We prove the \textbf{NP}-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the $n\times n$ rank-one matrices over $\{0,1\}$. The problems are: membership, rank of the decomposition, and a ``relaxed rank'' obtained from relaxing the zero-norm expression for the rank to an $\ell_1$ norm. While membership and rank are natural problems for any matrix cone, the relaxed rank problem occurs in some signal processing and statistical applications.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper pins down NP-hardness for membership, exact rank, and l1-relaxed rank on the correlation cone via standard Karp reductions.

read the letter

These results pin down the computational difficulty of three core problems on the correlation polytope: checking membership in the cone, finding the minimum number of rank-one factors, and doing the same with an l1 relaxation on the coefficients. The paper applies Karp reductions to transfer hardness from established NP-complete problems. This is a direct way to show intractability without needing new machinery. It does well by connecting the abstract cone to concrete applications in signal processing and statistics. The relaxed rank variant is particularly relevant because it appears in some estimation tasks where exact zero-norm is replaced by l1 for tractability, yet the paper shows even that stays hard. The reductions seem standard, but their correctness depends on careful construction to avoid creating easy special cases. Since the full details are in the paper, one would verify that the matrix constructions are polynomial-time and that no-instances map to matrices outside the cone or with higher rank. Any gap here would be the main concern, but the abstract gives no indication of issues. A minor point is that the paper might benefit from more discussion on how these hardness results affect existing algorithms or relaxations in the literature, but the core claims are clear. This work is aimed at the optimization community focused on discrete and combinatorial problems. Readers who need to know the limits of exact methods for correlation-based models will get value from it. I would recommend sending it for peer review. The topic is timely and the proofs, if sound, add to the body of knowledge on polyhedral complexity.

Referee Report

2 major / 1 minor

Summary. The manuscript proves the NP-hardness, via Karp reductions from known NP-hard problems, of three problems over the correlation cone (spanned by n x n rank-1 {0,1} matrices): membership testing, exact rank of the decomposition, and a relaxed rank obtained by replacing the zero-norm with an l1 norm. The relaxed-rank variant is motivated by applications in signal processing and statistics.

Significance. If the reductions are correct, the results establish that these natural problems on the correlation cone are computationally intractable, which has direct implications for optimization and approximation algorithms in the cited application domains. The use of standard Karp reductions from established NP-hard problems is a strength when the mappings are fully explicit and verified.

major comments (2)

[Abstract] The abstract asserts that Karp reductions exist for membership, exact rank, and relaxed-rank problems, but supplies neither the source NP-hard problems nor the explicit polynomial-time mappings. Without these constructions (presumably in the main body), it is impossible to confirm that the reductions are polynomial-time computable and that yes/no instances are preserved exactly for the correlation cone.
[Abstract] For the relaxed-rank problem, the l1 relaxation of the zero-norm must be shown to inherit hardness from the exact-rank problem via the same reduction; any gap where the l1 version becomes tractable on the image of the reduction would collapse the claim.

minor comments (1)

Notation for the correlation cone and polytope should be introduced with explicit definitions (e.g., the precise set of rank-1 generators) before the hardness statements.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review. The major comments are addressed point by point below, with references to the explicit constructions already present in the manuscript body.

read point-by-point responses

Referee: [Abstract] The abstract asserts that Karp reductions exist for membership, exact rank, and relaxed-rank problems, but supplies neither the source NP-hard problems nor the explicit polynomial-time mappings. Without these constructions (presumably in the main body), it is impossible to confirm that the reductions are polynomial-time computable and that yes/no instances are preserved exactly for the correlation cone.

Authors: The abstract serves as a concise overview, as is conventional. The source NP-hard problems and the full, explicit Karp reductions—including the polynomial-time mappings and the proofs that yes/no instances are preserved—are provided in the main body. Membership is treated via reduction in Section 3, exact rank in Section 4, and relaxed rank in Section 5. Each mapping is elementary (linear transformations of input matrices) and therefore polynomial-time, with direct verification that the correlation-cone membership and rank properties are preserved. revision: partial
Referee: [Abstract] For the relaxed-rank problem, the l1 relaxation of the zero-norm must be shown to inherit hardness from the exact-rank problem via the same reduction; any gap where the l1 version becomes tractable on the image of the reduction would collapse the claim.

Authors: The inheritance is established directly in the proof for the relaxed-rank result (Theorem 5). The reduction from the exact-rank problem is constructed so that, for every matrix in the image, the l1-relaxed rank equals the exact rank. This follows from the fact that the reduced instances lie at vertices of the correlation cone (sums of rank-1 {0,1} matrices); any feasible l1 solution of strictly smaller value would yield, by non-negativity and the cone geometry, a feasible 0-1 decomposition of lower rank, contradicting the exact-rank instance. Hence the decision problems coincide on the image and hardness transfers. revision: no

Circularity Check

0 steps flagged

No circularity: NP-hardness via standard Karp reductions from external problems

full rationale

The paper proves NP-hardness of membership, exact rank, and ℓ1-relaxed-rank problems on the correlation cone by constructing Karp reductions from known NP-hard problems. These reductions are polynomial-time mappings that preserve yes/no answers exactly and draw on external NP-completeness results rather than any self-referential definition, fitted parameter, or load-bearing self-citation. No step reduces by construction to the paper's own inputs; the derivation chain is self-contained against independent benchmarks of NP-completeness.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proofs rest on standard definitions of NP-hardness, Karp reductions, convex cones, and rank-one 0-1 matrices; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (1)

standard math Standard definitions of NP-completeness and Karp reductions from known hard problems
Invoked to establish hardness of the three target problems.

pith-pipeline@v0.9.0 · 5389 in / 1157 out tokens · 36469 ms · 2026-05-15T08:46:25.527359+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[1]

Bereg and M

S. Bereg and M. Haghpanah. Computing the Carath´ eodory number of a point. In M. Keil and D. Mondal, editors,Proceedings of the 32nd Canadian Conference on Computational Geometry, CCCG, pages 182–188, Saskatoon, 2020. University of Saskatchewan. REFERENCES 16

work page 2020
[2]

Berman and N

A. Berman and N. Shaked-Monderer.Completely Positive Matrices. World Scientific, Singapore, 2003

work page 2003
[3]

Blair and B

J. Blair and B. Peyton. An introduction to chordal graphs and clique trees. In A. Georgeet al., editor,Graph Theory and Sparse Matrix Computation, pages 1–29. Springer, New York, 1993

work page 1993
[4]

Bodlaender

H. Bodlaender. Dynamic programming on graphs with bounded treewidth. In T. Lepist¨ o and A. Salomaa, editors,International Conference on Automata, Languages and Programming (ICALP), volume 317 ofLNCS, pages 105–118, Berlin, 1988. Springer

work page 1988
[5]

Cand` es

E. Cand` es. The mathematics of sparsity. In S.Y. Jang, Y.R. Kim, D.-W. Lee, and I. Yie, editors, Proceedings of the International Congress of Mathematicians, volume I. Kyung Moon SA, Seoul, 2014

work page 2014
[6]

Cand` es and T

E. Cand` es and T. Tao. Decoding by Linear Programming.IEEE Transactions on Information Theory, 51(12):4203–4215, 2005

work page 2005
[7]

Caprara, F

A. Caprara, F. Furini, A. Lodi, M. Mangia, R. Rovatti, and G. Setti. Generation of antipodal random vectors with prescribed non-stationary 2-nd order statistics.IEEE Transactions on Signal Processing, 62(6):1603–1612, 2014

work page 2014
[8]

T. Chan, J. Cooper, M. Kouteck´ y, D. Kr´ al, and K. Pek´ arkov´ a. Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming.SIAM Journal on Computing, 51(3):664–700, 2022

work page 2022
[9]

B. P. Ching Li and M. Toulouse. Some NP-completenesss results on partial Steiner triple systems and parallel classes.Ars Combinatoria, 80:45–51, 2006

work page 2006
[10]

De Simone

C. De Simone. The cut polytope and the boolean quadric polytope.Discrete Mathematics, 79:71–75, 1990

work page 1990
[11]

Deza and M

M. Deza and M. Laurent.Geometry of Cuts and Metrics. Number 15 in Algorithms and Combina- torics. Springer, Heidelberg, 1997

work page 1997
[12]

R. Fortet. Applications de l’alg` ebre de Boole en recherche op´ erationelle.Revue Fran¸ caise de Recherche Op´ erationelle, 4:17–26, 1960

work page 1960
[13]

Gr¨ otschel, L

M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. Polynomial algorithms for perfect graphs.Annals of Discrete Mathematics, 21:325–356, 1984

work page 1984
[14]

Gr¨ otschel, L´ aszl´ o Lov´ asz, and Alexander Schrijver.Geometric algorithms and combinatorial optimization

M. Gr¨ otschel, L´ aszl´ o Lov´ asz, and Alexander Schrijver.Geometric algorithms and combinatorial optimization. Number 2 in Algorithm and Combinatorics. Springer, Berlin, 2nd edition, 1993

work page 1993
[15]

Kaibel and S

V. Kaibel and S. Weltge. A short proof that the extension complexity of the correlation polytope grows exponentially.Discrete and Computational Geometry, 53:397–401, 2015

work page 2015
[16]

Karzanov

A. Karzanov. Metrics and undirected cuts.Mathematical Programming, 32:183–198, 1985

work page 1985
[17]

Kloks.Treewidth Computations and Approximations

T. Kloks.Treewidth Computations and Approximations. Number 842 in LNCS. Springer, Berlin, 1994

work page 1994
[18]

Lund and M

C. Lund and M. Yannakakis. On the hardness of approximating minimization problems.Journal of the ACM, 41(5):960–981, 1994

work page 1994
[19]

Moitra.Algorithmic aspects of Machine Learning

A. Moitra.Algorithmic aspects of Machine Learning. CUP, Cambridge, 2018

work page 2018
[20]

Motzkin and E

T. Motzkin and E. Straus. Maxima for graphs and a new proof of a theorem of Tur´ an.Canadian Journal of Mathematics, 17:533–540, 1965

work page 1965
[21]

Murty and S

K. Murty and S. Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39:117–129, 1987. A ALTERNATIVE REDUCTION FOR THEC(n)RELAXED RANK17

work page 1987
[22]

Natarajan

B. Natarajan. Sparse approximate solutions to linear systems.SIAM Journal of Computing, 24(2):227–234, 1995

work page 1995
[23]

M. Padberg. The boolean quadric polytope: some characteristics, facets and relatives.Mathematical Programming, 45:139–172, 1989

work page 1989
[24]

Pitowsky

I. Pitowsky. Correlation polytopes: Their geometry and complexity.Mathematical Programming, 50:395–414, 1991

work page 1991
[25]

Preparata and M

F. Preparata and M. Shamos.Computational Geometry. Texts and Monographs in Computer Science. Springer, New York, 1985. Appendix A Alternative reduction for theC(n)relaxed rank LetKbe the complete undirected graph on the vertex setV(K) ={1, . . . , n}, with loops. We denote non-loop edges by{i, j} ∈E(K) and loops by the singletons{i}. Fory∈ {0,1} n we letY...

work page 1985