compressibility, Kolmogorov, learning

[Jagota Arun Kumar]

A short addition to the ongoing discussion thread of Juergen, Barak, and
David:

The following short paper is what intrigued us (K. Regan and I) to 
experimentally investigate the performance of algorithms on random versus 
compressible (i.e., structured) instances of the maximum clique optimization
problem.

@article{LiV92,
       author = "Li, M. and P.M.B. Vitanyi",
        title = "Average case complexity under the universal distribution equals worst-case complexity",
        pages = "145--149",
      journal =  "Information Processing Letters",
       volume =  42,
       month  =  "May",
         year =  1992
  }

In other words, roughly speaking, if one samples uniformly from the universal
distribution, one exhibits worst-case behavior of an algorithm.

I announced our (experimental, max-clique) paper on Connectionists a few 
months back, so won't do it again. However, this will be the subject of my 
talk at the NIPS workshop on optimization (7:30--8:00, Dec 1, Vail). Stop
by and jump all over me.

Arun Jagota