Sharpening Occam's Razor
  We provide a new representation-independent formulation of Occam's razor theorem, based on Kolmogorov complexity. This new formulation allows us to:   (i) Obtain better sample complexity than both length-based and VC-based versions of Occam's razor theorem, in many applications.   (ii) Achieve a sharper reverse of Occam's razor theorem than previous work.   Specifically, we weaken the assumptions made in an earlier publication, and extend the reverse to superpolynomial running times. 
Ming Li (Univ. Waterloo), John Tromp (CWI), and Paul Vitanyi (CWI and   University of Amsterdam)