Hopkins's formal low-degree conjecture for symmetric almost-independent distributions
Hopkins's formal low-degree conjecture for symmetric almost-independent distributions
Let be finite or , let be fixed, and let . Let be a product distribution on , let be another distribution on , and let denote the corresponding noisy or smoothed distribution. Suppose that is -invariant and -wise almost independent with respect to . Hopkins's Formal Low-Degree Conjecture. No polynomial-time test distinguishes from with probability for any ; formally, for every polynomial-time test there is such that the displayed average error is at most . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.