Complexity Theory

Machine Learning and Complexity Theory

A theoretical computer scientist's reflection on the relationship between machine learning and computational complexity theory after a Dagstuhl seminar — noting that the two fields remain largely disconnected despite studying adjacent phenomena. Raises questions about whether complexity theory has useful things to say about why ML works.