I have a hard time believing that any algorithm can replace what was taken out of the sound. Every sound is so unique. All the overtones are emphasized at different volumes. This is what makes every person, instrument, and thing sound different. This is very true when you have the same instrument played by different people. It'll sound different every time.
Of course, the mp3 can be improved upon by the algorithm filling in the gaps where clipping of the sound wave occurred. That I don't have a hard time believing.
-pat