Rigorous consequences of low-degree hardness
For distributions $\mathbb{P}_n$ and $\mathbb{Q}_n$ the low-degree advantage is $$\mathrm{Adv}^{\le D}_n = \max_{f\ \text{of degree} \le D} \frac{\mathbb{E}_{\mathbb{P}_n} f - \mathbb{E}_{\mathbb{Q}_n} f}{\sqrt{\operatorname{Var}_{\mathbb{Q}_n} f}}.$$ Hopkins's low-degree conjecture says, informally, that when it stays bounded for $D = (\log n)^{1 + \Omega(1)}$, with $\mathbb{Q}_n$ a product distribution and $\mathbb{P}_n$ invariant under relabelling, no polynomial-time algorithm distinguishes a noisy version of $\mathbb{P}_n$ from $\mathbb{Q}_n$. Holmgren and Wein refuted it for real-valued variables, and Buhai, Hsieh, Jain and Kothari refuted its quasi-polynomial form for Boolean variables. Hsieh, Kane, Kothari, Li, Mohanty and Tiegel proved rigorous implications of low-degree hardness in the vector and matrix cases.
Problem. Under which conditions on $\mathbb{P}_n$ and $\mathbb{Q}_n$ does a low-degree advantage that stays bounded for $D = (\log n)^{1 + \Omega(1)}$ as $n \to \infty$ rigorously imply that no polynomials of a certain degree can distinguish $\mathbb{P}_n$ from $\mathbb{Q}_n$?
Source: Kireeva, Open Problem 36 of Randomstrasse101, in “Low-degree hardness of finding the largest clique in Erdős–Rényi graph” (2026).
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- ST — Statistics Theory
- Secondary
- PR
- Keywords
- hypothesis testing, low-degree polynomials, Randomstrasse101, statistical-to-computational gaps
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{kireeva2026clique,
author = {Kireeva, Anastasia},
title = {Low-degree hardness of finding the largest clique in {E}rd{\H{o}}s--{R}{\'e}nyi graph (problems 36--38)},
howpublished = {Randomstrasse101 blog},
year = {2026},
url = {https://randomstrasse101.math.ethz.ch/posts/clique-low-degree/}
}
@phdthesis{hopkins2018thesis,
author = {Hopkins, Samuel B.},
title = {Statistical Inference and the Sum of Squares Method},
school = {Cornell University},
year = {2018}
}
@misc{holmgren2020lowdegree,
author = {Holmgren, Justin and Wein, Alexander S.},
title = {Counterexamples to the low-degree conjecture},
year = {2020},
eprint = {2004.08454},
archivePrefix = {arXiv}
}
@misc{buhai2025lowdegree,
author = {Buhai, Rares-Darius and Hsieh, Jun-Ting and Jain, Aayush and Kothari, Pravesh K.},
title = {The quasi-polynomial low-degree conjecture is false},
year = {2025},
eprint = {2505.17360},
archivePrefix = {arXiv}
}
@misc{hsieh2026rigorous,
author = {Hsieh, Jun-Ting and Kane, Daniel M. and Kothari, Pravesh K. and Li, Jerry and Mohanty, Sidhanth and Tiegel, Stefan},
title = {Rigorous implications of the low-degree heuristic},
year = {2026},
eprint = {2601.05850},
archivePrefix = {arXiv}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00049, "Rigorous consequences of low-degree hardness", clopen.solutions.