# Separation result for proper learning under the uniform vs. adversarial distributions?

Does anyone know of a concept class known to be (1) efficiently learnable under the uniform distribution but (1) NP-hard to learn under arbitrary [adversarial] distributions? I mean "learning" in the proper PAC sense.

Width-k conjunctions are NP hard to learn using halfspaces (and in particular using conjunctions) over arbitrary distributions, even for $k > \log(n)$: http://www.cs.cmu.edu/~yiwu/paper/mono.pdf
On the other hand, for $k \gg \log n$, width $k$ conjunctions are trivial to learn over the uniform distribution over examples using conjunctions, since every width-k conjunction will label a $1-1/2^k$ fraction of examples "0", so every width-k conjunction is a good hypothesis.
I would guess that there are similar examples that hold more broadly. Notice that easyness of learning over the uniform distribution holds for any "unbalanced" function, for the same trivial reason. Take a class of functions that is hard to learn even non-agnostically (poly-sized circuits, say). I would think that you could modify the lower-bound proof to hold even if you modify the circuits to be unbalanced: to evaluate to $1$ only on an $\epsilon$ fraction of random inputs. Meanwhile the hard distribution could still be one in which $\Pr[A(x) = 1] = 1/2$.
• Avrim Blum's answer via email: "2-term DNF. NP-hard for proper learning in general, but easy over the uniform distribution (find some $x_i$ s.t. $Pr(+|x_i=0) < Pr(+)$, and then $T_2 = {x_j : Pr(+ | x_i=0,x_j=0) = 0})$." – Aryeh Mar 14 '12 at 7:27