Hopkins's formal low-degree conjecture for symmetric almost-independent distributions

Let Ω\Omega be finite or R\mathbb R, let kk be fixed, and let N=(nk)N=\binom nk. Let ν\nu be a product distribution on ΩN\Omega^N, let μ\mu be another distribution on ΩN\Omega^N, and let TδμT_\delta\mu denote the corresponding noisy or smoothed distribution. Suppose that μ\mu is SnS_n-invariant and (logn)1+Ω(1)(\log n)^{1+\Omega(1)}-wise almost independent with respect to ν\nu. Hopkins's Formal Low-Degree Conjecture. No polynomial-time test distinguishes TδμT_\delta\mu from ν\nu with probability 1o(1)1-o(1) for any δ>0\delta>0; formally, for every polynomial-time test there is δ>0\delta'>0 such that the displayed average error is at most 1δ1-\delta'. This is a formalization of the low-degree heuristic under symmetry and almost-independence hypotheses.

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.