Hardness of approximation assuming the existence of one-way functions
The problem of learning in the PAC model is really just a problem of combinatorial optimization: with a large enough sample size, finding a function $f \in C$ which has low prediction error is equivalent to finding a function $f \in C$ which best classifies some finite sample from the distribution.

In this area, there are plenty of hardness of approximation results that depend on the existence of one-way functions. For example,
"Cryptographic Hardness of Distribution Specific Learning" -- Kharitonov, http://portal.acm.org/citation.cfm?id=167197

"Cryptographic limitations on learning Boolean formulae and finite automata" -- Kearns, http://portal.acm.org/citation.cfm?id=174647&amp;dl=GUIDE,

and many more recent results.