Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent

Matthew Brennan, Guy Bresler, Samuel B. Hopkins +2

Researchers currently use a number of approaches to predict and substantiate information-computation gaps in high-dimensional statistical estimation problems. A prominent approach…