I've read that Newton polynomials have better computational complexity, but Shamir's uses Lagrange polynomials instead. Does anyone know if there are particular reason why Newton polynomials aren't used instead?
I can only guess:
Other than that, Lagrange is easier to calculate than the difference methods, and is (probably rightly) regarded by many as the best choice when one already knows what polynomial degree will be needed. And when all the interpolation will be done at one x value, with only the data points' y values varying from one problem to another, Lagrange's formula becomes so much more convenient that it begins to be the only choice to consider.