{"id":"arxiv/2601.05850","url":"https://arxiv.org/abs/2601.05850","tags":["cs.CC","math.PR"],"score":0,"title":"Rigorous Implications of the Low-Degree Heuristic","domain":"cs.CC","source":"arxiv","authors":["Jun-Ting Hsieh","Daniel M. Kane","Pravesh K. Kothari","Jerry Li","Sidhanth Mohanty","Stefan Tiegel"],"reviews":0,"subject":"cs.CC","summary":"Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such results rely on the hypothesis that if the low-degree moments of the planted and null distributions are sufficiently close, then no efficient (noise-tolerant) algorithm can distinguish between them. This hypothesis is appealing due to the simplicity of calculating the low-degree likelihood ratio (LDLR) -- a quantity that measures the similarity between low-degree moments. However, despite sustained interest in the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-09","reactions":{}}