Complexity theoretic limitations on learning halfspaces

DOI10.1145/2897518.2897520zbMath1373.68262arXiv1505.05800OpenAlexW2140125566MaRDI QIDQ5361822

Amit Daniely

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

halfspaceshardness of learningrandom XOR

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Complexity theoretic limitations on learning halfspaces