Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)

DOI10.1145/3313276.3316301zbMath1433.68183arXiv1811.03491OpenAlexW2963546582MaRDI QIDQ5212820

Ilias Diakonikolas, Daniel M. Kane

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.03491

zbMATH Keywords

Fourier analysispolynomial threshold functionsrobust learningChow parameters

Mathematics Subject Classification ID

Computational learning theory (68Q32) Boolean functions (06E30) Boolean functions (94D10)