How simple can hard-to-learn functions be? The talk will survey a line of work on minimizing the computational complexity of cryptographic primitives, focusing mainly on the case of pseudorandom functions that imply hardness of learning.