Rigorous Implications of the Low-Degree Heuristic

Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari +3

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 r…