Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent.

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

Published in: COLT (2021)

Keyphrases

learning algorithm
noise tolerant
theoretical analysis
statistical queries
decision trees
worst case
noisy data
pac learning