Counterexamples to the Low-Degree Conjecture.

Justin Holmgren Alexander S. Wein

Published in: ITCS (2021)

Keyphrases

low degree
threshold functions
uniform distribution
decision lists
agnostic learning
pairwise
equivalence queries