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

2 comments:

Laurent Duval said...

I would have said: Minor, Minor, who's the sparsest in rank http://en.wikipedia.org/wiki/Minor_%28linear_algebra%29

Waldir said...

I cleaned this image up a bit: http://imgur.com/Qs61Q9s

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 :)

Printfriendly