Problems in NP but not in Average-P/poly The Karp–Lipton Theoem states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P_2}$ and $\mathsf{\Sigma^P_3}$, no $\mathsf{NP}$-complete problem will belong to $\mathsf{P/poly}$.

I'm interested in the following question:


  Assuming that $\mathsf{PH}$ does not collapse, or assuming any other reasonable assumption in structural complexity, what hard-on-average $\mathsf{NP}$ problems are proven not to lie in $\mathsf{Average\mbox{-}P/poly}$ (if any)?


A definition of $\mathsf{Average\mbox{-}P/poly}$ can be found in Relations between Average-case and Worst-case Complexity. Thanks to Tsuyoshi for pointing out that I actually need to use $\mathsf{Average\mbox{-}P/poly}$ instead of $\mathsf{P/poly}$.

I think there are problems such as (the decision versions of) FACTORING or DLOG which are conjectured to lie in $\mathsf{NP} - \mathsf{Average\mbox{-}P/poly}$, but the conjecture is not proven based on separations between complexity classes. (Please correct me if I'm wrong.)
This is a slightly improved version of my two comments on the question combined.

Let’s restrict our attention to distributional problems in DistNP (aka (NP, P-computable)) for simplicity.  Then you are looking for a problem in DistNP ∖ Average-P/poly.  Tautologically, such a problem exists if and only if DistNP ⊈ Average-P/poly.  And if DistNP ⊈ Average-P/poly, then every DistNP-complete problem lies outside Average-P/poly because Average-P/poly is closed under average-case reductions.

(Considering a larger class SampNP (aka (NP, P-samplable)) instead of DistNP does not change the situation much because DistNP ⊆ Average-P/poly if and only if SampNP ⊆ Average-P/poly.  This equivalence is a direct corollary of the result by Impagliazzo and Levin [IL90] that every distributional problem in SampNP is average-case reducible to some distributional problem in DistNP.)

I do not know which natural assumption implies DistNP ⊈ Average-P/poly.  The assumption that the polynomial hierarchy does not collapse is not known to imply even a weaker consequence that DistNP ⊈ Average-P, according to Section 18.4 of Arora and Barak [AB09]: “[…] even though we know that if P=NP, then the polynomial hierarchy PH collapses to P […], we don’t have an analogous result for average case complexity.”

References

[AB09] Sanjeev Arora and Boaz Barak.  Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

[IL90] Russell Impagliazzo and Leonid A. Levin.  No better ways to generate hard NP instances than picking uniformly at random.  In the 31st Annual Symposium on Foundations of Computer Science, 812–821, Oct. 1990.  http://dx.doi.org/10.1109/FSCS.1990.89604