Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent.

Matthew S. Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, Tselil Schramm

Browse the full COLT paper archive.