PAC algorithms for APX-Hard problems
If you had an approximation algorithm for an APX-hard problem which for any $\epsilon, \delta &gt;0$ runs in polynomial time and approximates the problem within a factor of $1+\epsilon$ with probability $1-\delta$, then $\mathsf{NP} \subseteq \mathsf{BPP}$. 

The reasoning is very similar to Chandra's answer to another question. APX-hardness for a problem $P$ implies that there is a PTAS reduction from instances of MaxSAT to instances of $P$: for every $\epsilon$, approximating Max3SAT to within a factor of $1+\epsilon$ is polynomial-time reducible to approximating $P$ to within a factor of $1 + c(\epsilon)$. By the PCP theorem, there is a constant $\epsilon_0$ such that the promise problem of distinguishing between satisfiable 3SAT instances and instances where at most a $1-\epsilon_0$ fraction of the constraints can be satisfied is NP-hard (in fact $\epsilon_0$ can be taken arbitrarily close to $1/8$, which is tight). Call this NP-hard promise problem $\text{Gap3SAT}(1, 1-\epsilon_0)$. The PTAS reduction from Max3SAT to $P$ with small enough $\epsilon$ (i.e. $\epsilon &lt; \frac{\epsilon_0}{1-\epsilon_0}$), together with the algorithm with "PAC guarantees", give a BPP algorithm for $\text{Gap3SAT}(1, 1-\epsilon_0)$, which implies a BPP algorithm for any problem in NP.