Learning with distributional inverters
  We generalize the "indirect learning" technique of Furst et. al., 1991 to
reduce from learning a concept class over a samplable distribution $\mu$ to
learning the same concept class over the uniform distribution. The reduction
succeeds when the sampler for $\mu$ is both contained in the target concept
class and efficiently invertible in the sense of Impagliazzo & Luby, 1989. We
give two applications.
  - We show that AC0[q] is learnable over any succinctly-described product
distribution. AC0[q] is the class of constant-depth Boolean circuits of
polynomial size with AND, OR, NOT, and counting modulo $q$ gates of unbounded
fanins. Our algorithm runs in randomized quasi-polynomial time and uses
membership queries.
  - If there is a strongly useful natural property in the sense of Razborov &
Rudich 1997 -- an efficient algorithm that can distinguish between random
strings and strings of non-trivial circuit complexity -- then general
polynomial-sized Boolean circuits are learnable over any efficiently samplable
distribution in randomized polynomial time, given membership queries to the
target function
