ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let G∼Gd(N,κ,q1,q2)G\sim\mathcal{G}_d(N,\kappa,q_1,q_2) be a hypergraphic planted dense subgraph with q1>q2q_1>q_2, adjacency tensor \mathbfcalA{\mathbfcal A}, and recovery error EHPDSR\mathcal{E}_{{\rm HPDS}_R}. HPDS recovery conjecture. If

lim inf⁡N→∞log⁡Nκ≥12\liminf_{N\to\infty}\log_N\kappa\geq\frac12

and

lim sup⁡N→∞log⁡N(κd−1(q1−q2)q2(1−q2))<d2−12,\limsup_{N\to\infty}\log_N\left(\frac{\kappa^{d-1}(q_1-q_2)}{\sqrt{q_2(1-q_2)}}\right)<\frac d2-\frac12,

then every randomized polynomial-time algorithm {ϕN}\{\phi_N\} satisfies

lim inf⁡N→∞EHPDSR(ϕN(\mathbfcalA))>12.\liminf_{N\to\infty}\mathcal{E}_{{\rm HPDS}_R}(\phi_N({\mathbfcal A}))>\frac12.

This conjecture says that the signal-to-noise requirement sufficient for the paper’s Aggregated-SVD recovery guarantee is also necessary for computationally efficient recovery in the stated regime. The source does not provide a resolution.

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.