ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let WW be a GOE(n)\mathrm{GOE}(n) matrix, let x∈{0,1}nx\in\{0,1\}^n have exactly kk nonzero entries, and observe Y=λkxx⊤+WY=\frac{\lambda}{k}xx^\top+W, with 1≪k≪n1\ll k\ll n. Exact recovery means outputting xx with probability tending to 11 as n→∞n\to\infty.

Sparse PCA runtime conjecture. For any λ\lambda in the hard regime

k/n≪λ≪min⁡{1,k/n},\sqrt{k/n}\ll\lambda\ll\min\{1,k/\sqrt n\},

any algorithm for exact recovery requires runtime

exp⁡(Ω~(k2λ2n)).\exp\left(\tilde\Omega\left(\frac{k^2}{\lambda^2n}\right)\right).

This conjecture proposes a precise computational barrier in the regime where exact recovery is believed to be information-theoretically possible but no polynomial-time algorithm is known. Existing evidence includes reductions from planted clique, failure of approximate message passing, sum-of-squares lower bounds, and the overlap gap property, but those results do not establish this precise optimal-runtime expression.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.