We present a deterministic algorithm to interpolate an m-sparse n-variate polynomial which uses poly(n,m,log H,log d) bit operations. Our algorithm works over the integers. Here H is a bound on the magnitude of the coefficient values of the given polynomial. This running time is polynomial in the output size. Our algorithm only requires black box access to the given polynomial, albeit in a special form. To our knowledge, this is the first algorithm in which number of bit operations have logarithmic dependence on the degree. As an easy consequence, we obtain an algorithm to interpolate polynomials represented by arithmetic circuits.