The cryptographic hardness of machine learning

This thesis investigates the use of cryptographic assumptions to obtain strong lower bounds on the ability of Probably Approximately Correct (PAC) algorithms to learn various concept classes over the Boolean domain and shows that there is no polynomial time prediction algorithm with membership queries for Boolean formulas, constant depth threshold circuits, and many other natural concept classes.