Sunday, September 25, 2011

Mirror, mirror, who's the sparsest of them all ?

The dark part shows the region where we think finding the sparsest solution to an underdetermined system of linear equations is NP. As time goes, it sure looks like this line is receding. In other words, for every new algorithms shown to work and busting the old limit, the territory of combinatorial problems shrinks and the NP vs P line in the sand shifts.

Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from


Laurent Duval said...

I would have said: Minor, Minor, who's the sparsest in rank

Waldir said...

I cleaned this image up a bit:

My current research touches CS, so should I find it appropriate to use this concept in an illustration, I'll build it as a svg diagram, and share it here :)