I've not seen any discussion of his paper yet, but the author has an impressive CV:

http://www.hpl.hp.com/personal/Vinay_Deolalikar/