A Proofs A.1 Learning D

For an overview of its proof, see Appendix B. Lemma A.1. In the following lemma, we use Lemma A.1 in order to show RSA T -hardness of By Assumption 2.1, there is K such that CSP K literals in the clause are satisfied by ψ, and otherwise null z, w null 1 . A.3 Hardness of learning random fully-connected neural networks Let n = ( n Let M be a diagonal-blocks matrix. By Lemma A.3, we have s By Lemma A.4, we have with probability 1 o Finally, Theorem 3.1 follows immediately from Theorem A.1 and the following lemma. By Lemma A.6, we have that By Theorem A.1, we need to show that SCAT We say that a distribution is isotropic if it has mean zero and its covariance matrix is the identity.