ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Fix a constant p∈(0,1)p\in(0,1). Let ntn_t and ktk_t be increasing sequences of positive integers such that kt=o(nt)k_t=o(\sqrt{n_t}) and ktk_t divides ntn_t, and let

At:Gnt→{0,1}\mathcal{A}_t:\mathcal{G}_{n_t}\to\{0,1\}

be a sequence of randomized polynomial-time algorithms. Under H0H_0, GG is sampled from the null distribution, while under H1H_1 it is sampled from the ktk_t-partite planted-clique distribution k-pc(nt,kt,p)k\text{-pc}(n_t,k_t,p). kk-partite planted clique conjecture. If GtG_t is an instance of k-pc(nt,kt,p)k\text{-pc}(n_t,k_t,p), then

lim inf⁡t→∞(PH0[At(G)=1]+PH1[At(G)=0])≥1.\liminf_{t\to\infty}\left(\mathbb{P}_{H_0}[\mathcal{A}_t(G)=1]+\mathbb{P}_{H_1}[\mathcal{A}_t(G)=0]\right)\geq 1.

Thus no such sequence of algorithms distinguishes the planted and null distributions with asymptotic error sum below 11; this is the formal hardness assumption used by the paper's reductions, and the source gives no 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.