The stronger secret-leakage planted clique conjecture

Let ρ\rho be sufficiently symmetric, and let pρ(s)p_\rho(s) denote the intersection-size distribution for two independent sets sampled from ρ\rho. Stronger Secret Leakage Planted Clique Conjecture. There is no polynomial-time algorithm solving \textscpcρ(n,k,1/2)\textsc{pc}_\rho(n,k,1/2) if some function w(n)=ωn(1)w(n)=\omega_n(1) exists such that the tail bounds of the Secret Leakage Planted Clique Conjecture hold for every dw(n)d\le w(n). This strengthens the usual conjecture by requiring the intersection-tail bounds only up to an arbitrary diverging degree parameter rather than up to polylogarithmic degree.

Sources & referencesView supporting material

Primary source

Matthew Brennan and Guy Bresler, “Reducibility and Statistical-Computational Gaps from Secret Leakage”, arXiv:2005.08099 (2020).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.