Hardness of approximation assuming the existence of one-way functions This question is inspired by a question posed by Shiva Kintali, Hardness of approximation assuming NP != coNP
. Multiplication of two prime numbers of equal size is strong candidate for one-way function. We know the $P \ne NP$ does not imply the existence of one-way functions.


  Are there any hardness of approximation results assuming the existence of one-way functions? 


Ideally, assuming $P \neq NP$ would not be sufficient to prove such hardness of approximation result and we must assume that existence of one-way functions to prove such hardness of approximation result.
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.