List Decodable Learning via Sum of Squares

DOI10.1137/1.9781611975994.10MaRDI QIDQ5146772zbMATH OpenOpenAlexFDO

Authors Prasad Raghavendra, Morris Yau

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(7)

• A moment-matching approach to testable learning and a new characterization of Rademacher complexity
• A characterization of list learnability
• Algorithms approaching the threshold for semi-random planted clique
• The rank of contextuality
• Distributionally robust optimization and robust statistics
• Polynomial-time sum-of-squares can robustly estimate mean and covariance of Gaussians optimally
• Robustly learning mixtures of k arbitrary Gaussians

This page was built for publication: List Decodable Learning via Sum of Squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146772)